グラフ | Notion

基本的なトピック

	UF	BFS	DFS
二部グラフ判定	倍化する
二部グラフでないとは、長さが奇数の閉路を持つことであることを利用する。	距離の偶奇が矛盾しないか判定	距離の偶奇が矛盾しないか判定
s-tパス判定
連結か判定
連結成分数
サイクル検出	union 操作で変化がない→サイクルがある	行きがけで訪問しているが帰りがけで訪問していない点にたどり着いたら、サイクルあり	入次数0の点を除くのを繰り返して、点が残る場合サイクルあり
(サイクルの頂点はすべて入次数が1以上)
トポロジカルソート	x	帰りがけ順の逆順を連結成分ごとに調べる	入次数0の点を除くのを繰り返す
頂点からの距離	x		x

サイクル: すべて入次数が1以上 or すべて出次数が1以上

すべての頂点の出次数が1の有向グラフ
性質
- 各連結成分には閉路がちょうど1つ存在する
  - ABC357 E - Reachability in Functional Graph の解説
- 頂点の数がnのとき、任意の頂点からn回進むと、閉路に入る
  - ABC311 C - Find it! の解説
関数からグラフを作る
- $X$ を有限集合として、関数 $f\colon X\to X$ を考える。$G = \{(x, f(x) \mid x\in X)\}$ とすると、$(X, G)$ は functional graph である。
  - $G$ は関数 $f$ のグラフと呼ばれていて、ややこしい
- $f$ の $k$ 回合成を $f^k$ と表すと、$(f^k(x))_{k=0}^\infty$ は途中（または最初）からループする（閉路に入る）
  - 応用例
    - べき乗 mod N の周期性代数学を使った整数論
    - 取れる石の数の種類が有限個与えられている Nim の grundy 数の周期性

無向グラフ
- 検出だけならUFを使えばOK
- 閉路の構成をする場合は、おそらくDFSなどが必要
  - 今の頂点だけじゃなくて、直前の頂点も持ったDFSが必要（逆走を防ぐために）
有向グラフ
- DFS をする
  - 行きがけ順で訪問済で、帰りがけ順では訪問していない点に訪問したら、閉路があることになる
  - 閉路を求めるには、行きがけでPush、帰りがけでPopをするStackを使うと良い（SCCと同様）