AtCoder NoviStepsを埋めてみる(29) サイクル検出の続きです。今回は二重辺連結成分分解です。
二重辺連結成分分解とは？
無向グラフで、2 つの頂点（u, v）の間にどの 1 本の辺を取り除いても両者は連結である場合、(u, v) は二重辺連結であるとだと考えます。グラフを二重辺連結である成分に分解することを二重辺連結成分分解といいます。またその辺が 1 本切れるだけで全体が連結ではなくなってしまう辺を「橋」（bridge）といいます。
道路や通信回線・送電線などが 1 箇所壊れてしまったときに孤立する部分ができないかを調べるときに使われるので、競技プログラミング以外でも有用性が高いアルゴリズムといえます。
どうやって橋を探すか？
橋はどうやって探せばよいのでしょうか？
この問題は実は辺をひとつずつ取り除いたグラフを構築し、それが連結グラフかどうか確認するという単純な方法で正解することができます。時間計算量は O(M(N + M)) です。
しかし難しい問題では O(M(N + M)) 解法では TLE してしまいます。実は O(N + M) 解法が存在します。それが Tarjan の橋検出アルゴリズム です。
Tarjan の橋検出アルゴリズムは以下のとおりです。
グラフから DFS木 を構築する。
辺(v, next)において next とその子孫から v の祖先に戻る辺が存在するかを調べる。存在するならその辺は橋ではない。
DFS木の各頂点 v に対して2つの値、ord[v] と low[v] を持たせます。
ord[v] は 頂点 v を深さ優先探索したときに最初に訪問した順番です。これに対して low[v] はDFS木の辺を 0 本以上下りた後、後退辺（祖先へ戻る辺）を 1 本使って到達できる祖先のうち、ord が最小のものです。
もし low[next] > ord[v] であれば next とその子孫から v より上の祖先へ戻ることができないので、辺(v, next) は橋です。
以下のコードで無向グラフの橋を全列挙することができます。注意点としてこのメソッドは辺を始点と終点で区別しているだけなので多重辺がある場合、橋を誤検出してしまいます。C – Bridge は多重辺が存在する入力はそもそもされないので問題ありませんが、そうではない場合は検出された橋のなかに同じものが存在しないか確認する処理が必要です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
class Program { // 無向グラフの橋を全列挙する static List<(int, int)> GetBridges(List<int>[] G) { int v_cnt = G.Length; int[] ord = new int[v_cnt]; // 頂点 v をDFSで最初に訪問した順番 int[] low = new int[v_cnt]; // 頂点 v の部分木からどこまでDFSの祖先へ戻れるか Array.Fill(ord, int.MaxValue); Array.Fill(low, int.MaxValue); List<(int, int)> bridges = new(); // 非連結グラフにも対応 for (int v = 0; v < v_cnt; v++) { if (ord[v] == int.MaxValue) DFS(v, -1, 0); } return bridges; void DFS(int v, int parent, int dist) { ord[v] = dist; foreach (int next in G[v]) { // DFS木の親への辺は無視 if (next == parent) continue; // 未訪問 if (ord[next] == int.MaxValue) { DFS(next, v, dist + 1); // 子から戻ってきた low[v] = Math.Min(low[v], low[next]); // low[next] と ord[v] の大小関係から橋かどうかを判定する if (low[next] > ord[v]) bridges.Add((v, next)); } // 訪問済み(v から DFSの祖先へ戻れる) else low[v] = Math.Min(low[v], ord[next]); } } } static void Main() { int[] nk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nk[0]; int M = nk[1]; List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) { G[i] = new List<int>(); } for (int i = 0; i < M; i++) { int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0] - 1; int b = ab[1] - 1; G[a].Add(b); G[b].Add(a); } var bridges = GetBridges(G); Console.WriteLine(bridges.Count); } } |
二重辺連結成分分解の結果を取得する
橋以外の辺で頂点を merge していけば二重辺連結成分分解をしたときの結果を取得することができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Program { static int[][] BridgeConnectedComponent(List<int>[] G) { var bridges = GetBridges(G); HashSet<string> set = new HashSet<string>(); foreach (var bridge in bridges) { set.Add($"{bridge.Item1},{bridge.Item2}"); set.Add($"{bridge.Item2},{bridge.Item1}"); } int v_cnt = G.Length; Dsu dsu = new Dsu(v_cnt); for (int i = 0; i < v_cnt; i++) { foreach (int next in G[i]) { if (!set.Contains($"{i},{next}")) dsu.Merge(i, next); } } return dsu.Groups(); } } |
二重辺連結成分をひとつの頂点に圧縮する
各二重辺連結成分を 1 個の巨大な頂点として扱うことを考えます。この橋だけを残したグラフは木になります。以下は二重辺連結成分をひとつの頂点に圧縮することで得られる木と各頂点の圧縮後の頂点番号を返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
class Program { // 二重辺連結成分をひとつの頂点に圧縮した「木」を得る static (List<int>[] Tree, int[] NewVertexNumber) GetBridgeBlockTree(List<int>[] G) { var bridges = GetBridges(G); HashSet<string> set = new HashSet<string>(); foreach (var bridge in bridges) { set.Add($"{bridge.Item1},{bridge.Item2}"); set.Add($"{bridge.Item2},{bridge.Item1}"); } int v_cnt = G.Length; Dsu dsu = new Dsu(v_cnt); for (int i = 0; i < v_cnt; i++) { foreach (int next in G[i]) { if (!set.Contains($"{i},{next}")) dsu.Merge(i, next); } } int[][] groups = dsu.Groups(); int[] beforeToAfters = new int[v_cnt]; for (int i = 0; i < groups.Length; i++) { int[] group = groups[i]; foreach (int v in group) beforeToAfters[v] = i; } HashSet<int>[] sets = new HashSet<int>[groups.Length]; for (int i = 0; i < groups.Length; i++) sets[i] = new HashSet<int>(); for (int i = 0; i < v_cnt; i++) { foreach (int next in G[i]) { int a = beforeToAfters[i]; int b = beforeToAfters[next]; if(a != b) // 縮約の結果、ループ辺が生じるので取り除く sets[a].Add(b); } } List<int>[] tree = new List<int>[groups.Length]; for (int i = 0; i < groups.Length; i++) tree[i] = sets[i].ToList(); return (tree, beforeToAfters); } } |
D – 旅行会社高橋君
問題の概要
N 個の頂点と M 本の辺からなる連結な単純無向グラフが与えられる。
始点、中継点、終点の 3 つの頂点が与えられる。同じ辺を通らずに始点から中継点を経由して終点にいたるパスがあるかを判定せよ。
同じ辺を通らずに始点から中継点を経由して終点にいたるパスが存在しないのは以下の場合です。
① 始点、終点がすべて同じ二重辺連結成分内にあり、中継点だけがこれとは異なる二重辺連結成分内にある
この場合、始点から中継点に移動するときと中継点から終点に移動するときに同じ橋を通るしかないので条件を満たしません。
② 始点、中継点、終点がそれぞれ異なる二重辺連結成分内にある場合で以下の条件をみたす場合
AC =（始点がある二重辺連結成分から終点がある二重辺連結成分への距離）
AB =（始点がある二重辺連結成分から中継点がある二重辺連結成分への距離）
BC =（中継点がある二重辺連結成分から終点がある二重辺連結成分への距離）
と定義したときに AC < AB + BC の場合（実は ① もこれに含まれるので ② だけ調べればよい）。
木の上で移動するとき AC < AB + BC となるのは、始点 → 中継点 → 終点に移動する過程で同じ辺を通ってしまうからです。
それ以外の場合は同じ辺を通らずに始点 → 中継点 → 終点へと移動することが可能です。
木の上にあるふたつの頂点間の距離と最小共通祖先
二重辺連結成分をひとつの頂点に圧縮したグラフを取得する自作メソッドは上に示したとおりですが、木の上にあるふたつの頂点間の距離を求めるにはどうすればよいでしょうか？ そのつど幅優先探索をしていては絶対に時間内には間に合いません。
根付き木の上にあるふたつの頂点間の共通の祖先のなかでもっとも距離が近くにあるものを最小共通祖先 (LCA) といいます。ふたつの頂点 u, v の LCA がわかるのであれば u, v 間の距離は（根から u までの距離）+（根から v までの距離）-（根から LCA までの距離の 2 倍）で計算することができます。
では LCA はどうやって求めればよいでしょうか？ ダブリングという手法を使います。
事前に「ある頂点から n 個上の祖先 は何か？」をすべて求めるのは現実的ではありません。そこで「ある頂点から 2^k 個上の祖先 は何か？」を求めておきます（ダブリング表を作る）。
深さ優先探索をすれば根から各頂点への距離（深さ）がわかります。そのあと
up[v][n] = v の 2^n 個上の祖先
となるように up に値を格納してダブリング表を作ります。
LCA を知りたいふたつの頂点 u, v が与えられたら、まず両者の深さを揃えます。例えば深さの差が 13 だったらまじめにひとつずつさかのぼる必要はありません。13 は 2^3 + 2^2 + 2^0 なので 2^3個上へ、2^2個上へ、2^0個上へ という 3 回の操作で処理を完了できます。
深さを揃えたら、次は 2 頂点を同時に 2^k だけ上へ移動させます。ただし移動した結果 u と v が同じになってしまうような移動はしません。このような移動は LCA を飛び越えて移動してしまう可能性があるからです。
2 頂点を同時に 2^k だけ上へ移動する動作は k が大きいものから試し、移動可能であることがわかったら実際に移動します。このような処理を繰り返すと u と v の親は同じになります。この親こそが求めようとしている LCA なのです。
LCA クラスを定義する
LCA を求めるために以下のクラスを定義します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
class LCA { List<int>[] Tree; int LOG; // 2^k を考えるとき k がとりうる最大値 int[][] up; // up[v][k] = vから2^k個上の祖先 int[] depth; // 各頂点の深さ public LCA(List<int>[] G) { int v_cnt = G.Length; Tree = G; LOG = 1; while ((1 << LOG) <= v_cnt) LOG++; up = new int[v_cnt][]; for (int v = 0; v < v_cnt; v++) up[v] = new int[LOG]; depth = new int[v_cnt]; DFS(0, 0); // ダブリング表を作る for (int k = 1; k < LOG; k++) { for (int v = 0; v < v_cnt; v++) up[v][k] = up[up[v][k - 1]][k - 1]; } } private void DFS(int v, int parent) { up[v][0] = parent; foreach (int next in Tree[v]) { if (next == parent) continue; depth[next] = depth[v] + 1; DFS(next, v); } } public int GetLCA(int u, int v) { // uの方が深くなるようにする if (depth[u] < depth[v]) (u, v) = (v, u); // 深さを揃える int diff = depth[u] - depth[v]; for (int k = 0; k < LOG; k++) { if (((diff >> k) & 1) != 0) u = up[u][k]; } // 同じ頂点なら、それがLCA if (u == v) return u; // 大きいジャンプから調べる for (int k = LOG - 1; k >= 0; k--) { if (up[u][k] != up[v][k]) { u = up[u][k]; v = up[v][k]; } } return up[u][0]; // u と v の親が LCA } // LCA を利用して u, v 間の距離を計算する public int GetDistance(int u, int v) { int lca = GetLCA(u, v); return depth[u] + depth[v] - 2 * depth[lca]; } } |
AC コード
二重辺連結成分分解と木上の二頂点間の距離を高速に取得できるようになったので問題を解きます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
class Program { // 二重辺連結成分分解してグラフを縮約する GetBridgeBlockTree(List<int>[] G) メソッドは上記定義のとおり static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) G[i] = new List<int>(); for (int i = 0; i < M; i++) { int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int x = xy[0] - 1; int y = xy[1] - 1; G[x].Add(y); G[y].Add(x); } var res = GetBridgeBlockTree(G); LCA lca = new LCA(res.Tree); int Q = int.Parse(Console.ReadLine()); List<string> ans = new List<string>(); for (int i = 0; i < Q; i++) { int[] abc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = abc[0] - 1; int b = abc[1] - 1; int c = abc[2] - 1; a = res.NewVertexNumber[a]; // 頂点番号を「木」の頂点番号に変換する b = res.NewVertexNumber[b]; c = res.NewVertexNumber[c]; if (lca.GetDistance(a, b) + lca.GetDistance(b, c) > lca.GetDistance(a, c)) ans.Add("NG"); else ans.Add("OK"); } foreach (string str in ans) Console.WriteLine(str); } } |
D – ハシポン
問題の概要
連結な無向単純グラフが与えられる。
橋をちょうど1本含む単純グラフをハシポングラフと定義する。
与えられたグラフに最小で何本の辺を追加したらハシポングラフになるかを求めよ。
橋が問題になっているので二重辺連結成分分解して二重辺連結成分を縮約して木を構築します。
木 のサイズが 1 のとき：”IMPOSSIBLE”
木 のサイズが 2 のとき：すでにハシポンなので 0 本
木 のサイズが 3 のとき：
もし木 のどの頂点も、ただ 1 個の頂点からなるとき：”IMPOSSIBLE”（単純性を破壊してしまうため）
そうでないとき：辺を 1 本追加してハシポンにできるので、1 本
木 のサイズが 4 以上のとき：（後述）
木 のサイズが 4 以上のときの判定方法ですが、葉の数 (leaf_count) に着目します。
最小本数の辺を挿入してハシポンにするためには、基本的には「葉」同士を結んでいけば良いです。辺を追加したあと葉が複数あるときは橋も複数存在します。適切に葉を選べば辺を追加することで葉がなくなったときは橋もなくなっています。橋はひとつだけ残したいので、葉の数が偶数のときは最後に追加する辺の片方を葉からずらします。なので leaf_count が偶数のときは leaf_count / 2 が答えです。
奇数のときは leaf_count / 2 本の辺を追加した段階で葉がひとつ残ります。このとき最後の葉が、2 本以上の橋をつないだ先端にある場合はもう 1 本辺を追加する必要があります。葉をひとつ取ったときに木の葉を減らすことができるものが一つでもあれば leaf_count / 2 が答えですが、そうでないなら leaf_count / 2 + 1 が答えです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
class Program { // GetBridgeBlockTree(List<int>[] G) メソッドは上記定義のとおり static void Main() { int[] nk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nk[0]; int M = nk[1]; List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) G[i] = new List<int>(); for (int i = 0; i < M; i++) { int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int x = xy[0]; int y = xy[1]; G[x].Add(y); G[y].Add(x); } var tree = GetBridgeBlockTree(G).Tree; if (tree.Length == 1) Console.WriteLine("IMPOSSIBLE"); else if (tree.Length == 2) Console.WriteLine(0); else if (tree.Length == 3) { if (N == 3) Console.WriteLine("IMPOSSIBLE"); else Console.WriteLine(1); } else { int leaf_count = 0; bool exist = false; // 葉をひとつ取ったときに木の葉を減らすことができる foreach (var nexts in tree) { if (nexts.Count == 1) { leaf_count++; if(tree[nexts[0]].Count >= 3) exist = true; } } if (leaf_count % 2 == 0) Console.WriteLine(leaf_count / 2); else { if(exist) Console.WriteLine(leaf_count / 2); else Console.WriteLine(leaf_count / 2 + 1); } } } } |
