強連結成分分解とは？
強連結成分（SCC, Strongly Connected Component）とは、有向グラフにおいて互いに行き来が可能な頂点の集合のことです。強連結成分分解とは、強連結成分を1つの頂点にまとめること。こうしてまとめられた頂点でグラフを再構築すると、その有向グラフはDAG（directed acyclic graphs：閉路がない有向グラフ）になります。
強連結成分分解をするにはどうすればよいでしょうか？
まず、深さ優先探索をして各頂点に帰り掛け順でID（0 から 成分数-1）を振ります。
そのあとグラフを辺の向きをすべて反転して、IDの大きいものから再度深さ優先探索をして、一度でたどり着けるところをそれぞれ強連結成分とします。
ではやってみましょう。
021 – Come Back in One Piece（★5）
021 – Come Back in One Piece（★5）
N 頂点 M 辺の有向グラフがあります。辺には 1, 2, …, M と番号が付けられており、辺 i は頂点 A_i から頂点 B_i に向かいます。
次の条件を満たす 2 頂点 (x, y) の組 (1 ≦ x ＜ y ≦ N) はいくつありますか？
頂点 x から頂点 y に向かうパス、頂点 y から頂点 x に向かうパスがどちらも存在する
入力されるデータ
N M
A_1 B_1
A_2 B_2
…
A_M B_M（ただし、2 ≦ N ≦ 100000
1 ≦ M ≦ 200000
1 ≦ A i, B i ≦ N, A_i ≠ B_i）
強連結成分分解すればその内部では「頂点 x から頂点 y に向かうパス、頂点 y から頂点 x に向かうパスがどちらも存在」します。頂点 (x, y) の組ですが、これはひとつの強連結成分の頂点の数を a とすると a * (a – 1) / 2 で計算することができます。
まず頂点の番号と割り当てたIDをセットにして扱いたいので Vertex クラスを定義します。
|
1 2 3 4 5 6 7 8 9 10 |
class Vertex { public Vertex(int num, int id) { Number = num; ID = id; } public int Number = 0; public int ID = 0; } |
次に深さ優先探索で帰り掛け順にIDをふるためのメソッドを定義します。一度訪問した頂点をまた訪問してしまうといつまで経っても終わらないので visits で制御します。
|
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 |
public class Program { static bool[] visits = { }; static int nextId = 0; static Vertex[] vertices = { }; static void Dfs1(int vNum, List<int>[] list) { if (!visits[vNum]) { visits[vNum] = true; dfs(vNum); } void dfs(int num) { foreach (int i in list[num]) { if (visits[i]) continue; visits[i] = true; dfs(i); } vertices[num] = new Vertex(num, nextId++); } } } |
強連結成分分解するためには、頂点のIDが確定したらIDが大きいものから再度深さ優先探索をして、一度でたどり着けるところをそれぞれ強連結成分とするのでした。その処理を示します。
|
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 |
public class Program { static List<int> Dfs2(int vNum, List<int>[] list) { List<int> rets = new List<int>(); // たどり着ける頂点をリストにして返す if (!visits[vNum]) // 一度訪問した頂点は対象外 { rets.Add(vNum); visits[vNum] = true; dfs(vNum); } return rets; void dfs(int num) { foreach (int i in list[num]) { if (visits[i]) continue; visits[i] = true; dfs(i); rets.Add(i); } } } } |
上記で定義したメソッドを用いて強連結成分分解をして解を求めます。
|
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 |
public class Program { static void Main() { int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } // 連結リストと辺を逆にした連結リストを生成する List<int>[] list = new List<int>[N]; List<int>[] rlist = new List<int>[N]; for (int i = 0; i < N; i++) { list[i] = new List<int>(); rlist[i] = new List<int>(); } for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; list[a].Add(b); rlist[b].Add(a); } visits = new bool[N]; vertices = new Vertex[N]; // 帰り掛け順で ID をつける for (int i = 0; i < N; i++) Dfs1(i, list); // ID が大きい順にソート vertices = vertices.OrderByDescending(_ => _.ID).ToArray(); long ans = 0; // N が大きいので int だとオーバーフローする visits = new bool[N]; foreach (Vertex vertex in vertices) { List<int> rets = Dfs2(vertex.Number, rlist); ans += 1L * rets.Count * (rets.Count - 1) / 2; } Console.WriteLine(ans); } } |
トポロジカルソート
グラフが DAG（directed acyclic graphs：閉路がない有向グラフ）だった場合、IDを割り振った段階でトポロジカルソートの逆をしたことになっています。IDを大きい順に並べ替えればトポロジカルソートになります。
ただし、トポロジカルソートができる条件はグラフが DAG であることなので、IDを割り振っただけでトポロジカルソートをしたつもりになってはいけません。
D – 最悪の記者
リーグ戦の対戦結果の結果の一部が与えられる。
情報 1 引き分けの試合はなかった。
情報 2 全てのチームに異なる順位がついた。
情報 3 ある a ＜ b を満たすふたつの整数があった場合、 a 位のチームと b 位のチームの試合では 必ず a 位のチームが勝利した。入力として一部の試合の勝敗が与えられたとき、伝えられた情報に適合する順位表（1 位から n 位の順にチームを並べたもの）を 1 つ出力するプログラムを作れ。また出力した順位表以外に伝えられた情報に適合する順位表が存在するかどうかも判定せよ。
入力されるデータ
N
M
A_1 B_1
A_2 B_2
…
A_M B_Mただし、
N はチームの総数（1 ≦ n ≦ 5,000）
M は与えられる試合の結果数（1 ≦ M ≦ 100,000）
A_i B_i は A_i が B_i に勝ったことを意味する出力
i 行目 (1 ≦ i ≦ n) に i 位のチームの番号を出力せよ。
最後の行には出力した順位表以外に伝えられた情報に適合する順位表が存在するかどうかを表す整数を出力せよ。存在しなければ 0、存在する場合は 1 を出力せよ。
各チームを頂点として勝ったチームから負けたチームに辺を張って有向グラフを生成した場合、トポロジカルソートすれば順位を知ることができます。また 情報 3 より必ずトポロジカルソートできることが保証されています。またこの問題では得られたトポロジカルソート順が唯一かどうかも判定しなければなりません。
では、トポロジカルソート順が唯一かどうかはどうやって判定すればよいのでしょうか？
一般に、トポロジカルソート順において、ある連続する 2 要素の間に辺がないとき、その 2 要素を入れ替えることができてしまいます。
ということはとりあえずトポロジカルソートしてみて順位が連続するチームの間に対戦情報があるかどうかを調べればよいということになります。
|
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 |
using System; using System.Collections.Generic; using System.Linq; public class Program { static bool[] visits = { }; static Vertex[] vertices = { }; static int nextId = 0; // Vertex クラスは同じなので省略 // Dfs1 メソッドも同じなので省略 static void Main() { int N = int.Parse(Console.ReadLine()); int M = int.Parse(Console.ReadLine()); List<int>[] list = new List<int>[N]; List<int>[] rlist = new List<int>[N]; for (int i = 0; i < N; i++) { list[i] = new List<int>(); rlist[i] = new List<int>(); } for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; list[a].Add(b); rlist[b].Add(a); } visits = new bool[N]; vertices = new Vertex[N]; for (int i = 0; i < N; i++) Dfs1(i, list); // ID で降順ソートすれば各チームが順位ごとに並べ替えることができたことになる vertices = vertices.OrderByDescending(_ => _.ID).ToArray(); // 1位からチーム番号を取得していく List<int> ranks = new List<int>(); foreach (Vertex vertex in vertices) ranks.Add(vertex.Number); // トポロジカルソート順が唯一かどうかチェック（findAll == true なら唯一） bool findAll = true; for (int i = 0; i < ranks.Count - 1; i++) { int a = ranks[i]; int b = ranks[i + 1]; if (list[a].IndexOf(b) == -1 && list[b].IndexOf(a) == -1) { findAll = false; break; } } foreach (int r in ranks) Console.WriteLine(r + 1); // チーム番号は 1 から始まるので if(findAll) Console.WriteLine(0); else Console.WriteLine(1); } } |
