強連結成分分解とは?

強連結成分(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 クラスを定義します。

次に深さ優先探索で帰り掛け順にIDをふるためのメソッドを定義します。一度訪問した頂点をまた訪問してしまうといつまで経っても終わらないので visits で制御します。

強連結成分分解するためには、頂点のIDが確定したらIDが大きいものから再度深さ優先探索をして、一度でたどり着けるところをそれぞれ強連結成分とするのでした。その処理を示します。

上記で定義したメソッドを用いて強連結成分分解をして解を求めます。

トポロジカルソート

グラフが DAG(directed acyclic graphs:閉路がない有向グラフ)だった場合、IDを割り振った段階でトポロジカルソートの逆をしたことになっています。IDを大きい順に並べ替えればトポロジカルソートになります。

ただし、トポロジカルソートができる条件はグラフが DAG であることなので、IDを割り振っただけでトポロジカルソートをしたつもりになってはいけません。

D – 最悪の記者

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 要素を入れ替えることができてしまいます。

ということはとりあえずトポロジカルソートしてみて順位が連続するチームの間に対戦情報があるかどうかを調べればよいということになります。