はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける無向グラフに関する(橋、関節点、サイクル基底、lowlink)問題まとめ

無向グラフへの取り組み

  • 二重辺連結成分分解と橋
    • 橋とはその辺をなくすと連結でなくなる辺のこと
    • 二重辺連結成分とは橋を含まない頂点集合のこと
    • 無向グラフを二重辺連結成分に分解する よく分かる解説
    • 各成分内では、任意の3頂点を取ってきた時にa->b->cとなる辺素パス(同じ辺を2回使わない)が存在する
    • 各成分を縮約して1つの頂点とすると、無向グラフは木に変換される
  • 二重頂点連結成分分解と関節点
    • vertex biconnected components
    • 関節点とはその頂点をなくすと連結でなくなる辺のこと
    • 二重頂点連結成分とはこの分かりやすいイメージのように成分分解すること
    • ある頂点が複数の成分に属する場合がある(関節点は複数の成分に属する)
    • 全ての単純サイクルが奇数長だけであるグラフは、すべての二重頂点連結成分が橋または単純サイクルをなすcactus graphになる 解説と問題
    • In a biconnected graph with n ≥ 3 points, for any three different vertices a, b, c, there is a simple path to from a to b going through c.
    • これも各成分を縮約すると、木となるが、Block-Cut Treeと言うらしい
    • lowlink(参考)を知っていると良い(lowlinkを知ってると良い問題 その2)
  • サイクル基底
    • cycle basis, 無向グラフのサイクルについての理論
    • 日本語で競プロ向けに書いてあるのはKUPC2012のKの解説
    • 無向グラフを好きなルートで回って特定の所に行く時の最適化で使える
    • dfsを1回することでサイクル基底が得られる。xorの場合は、ガウスの消去法を使うことでサイクル基底の個数を更に減らすことができる
  • サイクルの偶奇による分類
    • 偶数長サイクルだけのグラフは二部グラフである
    • 奇数長サイクルだけのグラフはcactusといい、全ての二重頂点連結成分は橋かサイクルになる 解説と問題
      • cactusグラフでは辺を共有する閉路は存在しない(つまり、閉路の全列挙が現実的な時間でできる)問題
  • dfs木
    • 無向グラフをdfs順で回っていって使った辺のみで構築した木
    • 後退辺をうまく使いながら処理していく
  • スペクトルグラフ理論
  • エルデシュガライの定理
  • 木を最小パスで被覆する問題に対する解法
    • 参考
    • 「辺の重複あり」適切に葉同士で繋ぐ
    • 「辺の重複無し」奇数次の点に適当に辺を張ってオイラー閉路作って切っていく
  • 全ての辺について端点のどちらかを選択する。このときに、2つ以上の辺に選択されている頂点が存在しないようにせよ
    • 連結成分において、(辺の数)≦(頂点の数)であればよい
    • 問題1 問題2

競技プログラミングにおけるオイラー路問題まとめ

オイラー

  • 無向・有向グラフ上で一筆書きをするパスのこと
  • 存在条件があり、dfsで構築可能 参考1 参考2

Twitterで見つけただけ

オイラー路(復元も?)

CupShuffle [yukicoder 429]

問題

http://yukicoder.me/problems/no/429

N個のコップがあり、K回2つのコップを入れ替える作業を行うがが、
X回目の作業で入れ替えたコップの位置だけ分からないので、答えよ。

入れ替え作業の流れは以下の通り。

  • 最初、位置iにはコップiがある
  • i回目の交換ではA[i]の位置とB[i]の位置のコップを入れ替える
  • 最終的に、位置iにはコップC[i]がある

2 <= N <= 10^5
1 <= K <= 10^5

続きを読む

FromToDivisible [SRM 699 : Div1 Med]

問題

1~Nの番号がついているグラフがある。
ここでM組のa[i]とb[i]が与えられる。
「XからYへの辺がある」⇔「Xがa[i]の倍数かつYがb[i]の倍数」で辺がある。
このとき、始点Sから始点Tまでの最短距離は?
もし到達不可能なら-1

2 <= N <= 10^9
1 <= M <= 10^3

続きを読む

Sonya and Queries [Codeforces 371 : Div1 A, Div2 C]

問題

http://codeforces.com/contest/713/problem/A

t個のクエリを処理する。

1. + a : 自然数aをmultisetに入れる
2. - a : 自然数aをmultisetから1つ消す
3. ? s : 文字列sのパターンに当てはまる自然数aがmultisetに何個あるか出力する

文字列sのパターンとは、
010であれば、偶数・奇数・偶数と各桁なっている数を指す(414など)
もし、文字列の方が数より長さが小さいなら、文字列の先頭に0を追加して判断する
もし、数の方が文字列より長さが小さいなら、数の先頭は0であるものとして考える

1 <= t <= 10^5
0 <= a <= 10^18
1 <= |s| <= 18

続きを読む