[問題案] st-numbering

[maspypy]

問題概要

(N, M) 無向単純グラフ $G$ と、始点 $s$, 終点 $t$ が与えられる。

順列 $p = (p_v)_v$ であって以下を満たすものの存在判定・構築。

• 各辺を、 $p_u < p_v$ のときに $u$ から $v$ を向き付けたとする。このとき、任意の頂点 $v$ に対して、 $v$ を通る $st$ パスが存在する。

制約

• $2\leq N\leq 10^5$
• $s\neq t$
• $0\leq M\leq 10^5$
• 単純グラフ

資料

• https://en.wikipedia.org/wiki/Bipolar_orientation
• https://www.luogu.com.cn/blog/user19567/yi-dao-tu-lun-ti-ji-ji-yan-sheng

dfs してpreorder, lowlink あたりをいじればできて、線形時間。

出題例

ac.nowcoder.com/acm/contest/33188/F

（$s, t$ ごとに存在判定するクエリ）

ac.nowcoder.com/acm/contest/33192/H

（構築+別の既出）

定式化について

たとえば上述の wikipedia によれば、

• bipolar orientation とは、辺を向き付けて DAG にする方法であって、唯一の source $s$ と sink $t$ を持つもの
• $st$-numbering とは、頂点の番号付けであって、任意の $v\notin {s,t}$ が番号の小さい点とも大きい点とも隣接するもの

とあって、これらが同値であると書かれている。が、$N=2$ で辺が存在しない場合に同値性が壊れている。上に書いた問題概要では、前者の定式化を採用している（$N=2$ で辺が存在しない場合は NG）。

[noshi91]

多重辺あり非連結あり自己ループ無しが良い気がしました。 https://github.com/yosupo06/library-checker-problems/blob/master/docs/style.md

[maspypy]

作業者募集。