Strongly Connected Components
有向グラフには、0 から n-1 まで番号が付けられた n 個のノードと、edges のリストがあります。ここで [from, to] は、ノード from からノード to への辺を表します。
強連結成分とは、辺をたどることで各ノードから他のすべてのノードに到達できる、最大のノードのグループです。各ノードはちょうど1つの成分に属し、どのサイクルにも属さないノードはそれ自体で1つの成分を形成します。強連結成分の数を返してください。
関数
- ninteger
- ノードの数
- edgesinteger-2d-array
- 有向辺をそれぞれ [from, to] として
- 戻り値integer
- 強連結成分の数
制約
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [from, to]であり、0 ≤ from, to < nかつfrom ≠ to- 同じ辺が2回現れることはありません。
例
- 入力
- n = 6edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
- 出力
- 3
- 説明
- ノード 0、1、2 はループを形成しているため、互いに到達できます。ノード 3 と 4 は互いを指しています。ノード 5 からは 4 に到達できますが、5 に戻る経路はないため、5 は単独です。つまり、コンポーネントは 3 つです。
- 入力
- n = 5edges = [[1, 0], [0, 1], [2, 3]]
- 出力
- 4
- 説明
- ノード 0 と 1 は互いに指し合っており、1つの連結成分を形成しています。2 から 3 への辺は一方向のみなので、2 と 3 は別々の連結成分です。また、ノード 4 には辺がまったくありません。連結成分は4つです。
発展問題
グラフ全体を1つの強連結成分にするには、辺を最低何本追加する必要がありますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
2つのノードが同じ連結成分に属するのは、それぞれがもう一方に到達できる場合に限ります。すべてのノードから探索すれば確認できますが、同じ辺を何度もたどることになります。1回の深さ優先探索で、連結成分の始まりについて何がわかるでしょうか？
深さ優先探索で最初に到達した順に、ノードに番号を付けます。各ノードについて、
lowも追跡します。これは、探索木を下り、その後1つの辺をたどって、まだ開いている成分のノードに戻ることで到達できる最小の番号です。lowが自身の番号と等しいノードは、その成分の最初のノードです。訪問済みのノードをスタックに保持します。ノードの処理が終わり、
lowがそのノード自身の番号と等しい場合は、そのノードまでスタックから取り出します。それらのノードが1つの成分を形成するので、数を数えます。あるテストでは探索の深さが5000ノードになるため、再帰する代わりに、(ノード、次の辺)のフレームを格納する独自のスタックを使います。
解説
各連結成分を一点に縮約すると、連結成分は閉路のないグラフを形成します。Kosaraju法とTarjan法はこれを利用して、すべての連結成分を O(n + E) で見つけます。ここで E は辺の数です。
すべてのノードから前方および後方に検索する
正しいが、最大のテストでは終わらない
考え方
ノード u と v が同じ連結成分に属するのは、それぞれがもう一方に到達できる場合に限ります。したがって、まだ連結成分が決まっていないノード s について、辺に沿って前向きに探索し、逆向きの辺に沿って後ろ向きに探索します。両方の探索で見つかったノードが、そのノードの連結成分です。最初の例では、0から前向きに探索すると0から4までが見つかり、後ろ向きに探索すると0、1、2が見つかるため、{0, 1, 2}が1つの連結成分になります。
各連結成分の判定では、グラフの大部分に対して2回の探索が必要です。5001個のノードを通る5000本の辺の連鎖では、各ノードがそれぞれ独立した連結成分となり、探索では約2.5 × 10^7個のノードを訪れます。
アルゴリズム
- すべてのノードの出辺リストと入辺リストを作成します。
- コンポーネントに属していない次のノード
sを選び、新しいコンポーネントを数えます。 - 出辺をたどって
sから到達できるノードと、入辺をたどってsに到達できるノードに印を付けます。 - 両方の探索で印が付いたノードはすべて、
sのコンポーネントに加わります。すべてのノードがいずれかのコンポーネントに属したら、その数を返します。
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
done = [False] * n
# fwd[v] == s: the search forward from s reached v. bwd[v] == s: v reaches s.
fwd = [-1] * n
bwd = [-1] * n
count = 0
for s in range(n):
if done[s]:
continue
count += 1
# Every node s can reach.
fwd[s] = s
reached = [s]
stack = [s]
while stack:
node = stack.pop()
for nxt in out[node]:
if fwd[nxt] != s:
fwd[nxt] = s
reached.append(nxt)
stack.append(nxt)
# Every node that can reach s.
bwd[s] = s
stack = [s]
while stack:
node = stack.pop()
for prev in rev[node]:
if bwd[prev] != s:
bwd[prev] = s
stack.append(prev)
# The nodes found both ways form the component of s.
for v in reached:
if bwd[v] == s:
done[v] = True
return countコサラジュのアルゴリズム：2回の走査
考え方
成分グラフでは、出ていく辺がない成分がシンクとなり、その内部から探索を始めると、その成分だけが見つかります。Kosarajuのアルゴリズムは、各探索がそのように動作するように順序を決めます。
第1パスでは、各ノードの深さ優先探索が終了したときに、そのノードをすべて記録します。第2パスでは、同じ成分を持つ逆向きグラフを、終了順が最後のノードから探索します。成分BからCに辺が向かっている場合、Bの最後のノードはCのすべてのノードより後に終了します。そのため、第2パスがCに到達したとき、Cに辺が入る成分はすべて割り当て済みであり、逆向きグラフでは探索がCの外へ出ることはできません。
最初の例では、ノードは4、3、2、1、0、5の順に終了します。第2パスでは、まず{5}、次に{0, 1, 2}、最後に{3, 4}が集められます。
アルゴリズム
- 出辺リストと入辺リストを作成します。
- 未訪問の各ノードから反復的な深さ優先探索を実行し、探索が終了したノードをそれぞれ
orderに追加します。 orderを末尾からたどります。成分が割り当てられていないノードごとに、新しい成分を数え、そのノードから入辺に沿って探索し、到達した未割り当てのノードすべてに成分を割り当てます。個数を返します。
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
# Pass 1: depth first search on the graph, listing each node when it finishes.
seen = [False] * n
order = []
for start in range(n):
if seen[start]:
continue
seen[start] = True
# Each frame is [node, next edge to try].
stack = [[start, 0]]
while stack:
frame = stack[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if not seen[nxt]:
seen[nxt] = True
stack.append([nxt, 0])
else:
stack.pop()
order.append(node)
# Pass 2: on the reversed graph, start from the last node to finish.
# Each search collects exactly one component.
done = [False] * n
count = 0
for start in reversed(order):
if done[start]:
continue
count += 1
done[start] = True
stack = [start]
while stack:
node = stack.pop()
for prev in rev[node]:
if not done[prev]:
done[prev] = True
stack.append(prev)
return countTarjanのアルゴリズム：low値を使った1回の走査
考え方
深さ優先探索を1回実行し、各頂点に到達した順番で番号を付けます。それがその頂点の index です。成分がまだ確定していない訪問済み頂点をスタックに保持し、さらに値 low を保持します。これは、探索木を下ってからスタック上の頂点へ戻る1本の辺をたどって到達できる、最小の番号です。
頂点の処理が終わったとき、low が index より小さければ、その下にある頂点から、より前に到達した未確定の頂点へ戻れるため、その頂点はスタックに残ります。両者が等しい場合、その頂点は探索がその成分で最初に入った頂点です。スタックからその頂点までを取り出し、成分を1つ数えます。取り出し済みの頂点へ向かう辺は、戻って到達できない確定済みの成分につながるため、無視します。
最初の例では、3を処理すると {4, 3} が取り出され、0を処理すると {2, 1, 0} が取り出されます。頂点5の辺は、すでに取り出された4へ向かうため、5だけが取り出されます。
アルゴリズム
- 未訪問の各ノードに次のインデックスを割り当て、
lowを同じ値に設定し、ノードスタックにプッシュして、フレーム（ノード、最初の辺）をプッシュします。 - 最上位フレームのノードに未確認の辺が残っている場合は、それをたどります。未訪問のターゲットにはインデックスとフレームを割り当て、ノードスタック上にあるターゲットの場合は、
low[node]をそのインデックスまで下げます。 - そうでなければフレームをポップし、親の
lowをlow[node]まで下げます。low[node]がindex[node]と等しい場合は、ノードスタックからそのノードまでポップし、1つの連結成分として数えます。
def countSCC(n, edges):
out = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
index = [-1] * n # discovery time, -1 while unvisited
low = [0] * n # earliest discovery time the node can reach and still return from
on_stack = [False] * n
stack = [] # visited nodes whose component is still open
time = 0
count = 0
for start in range(n):
if index[start] != -1:
continue
index[start] = low[start] = time
time += 1
stack.append(start)
on_stack[start] = True
# The depth first search keeps its own call stack: [node, next edge to try].
calls = [[start, 0]]
while calls:
frame = calls[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if index[nxt] == -1:
index[nxt] = low[nxt] = time
time += 1
stack.append(nxt)
on_stack[nxt] = True
calls.append([nxt, 0])
elif on_stack[nxt]:
# An edge back into an open component.
low[node] = min(low[node], index[nxt])
else:
calls.pop()
if calls:
parent = calls[-1][0]
low[parent] = min(low[parent], low[node])
# Nothing below node reaches above it: node closes a component.
if low[node] == index[node]:
count += 1
while True:
w = stack.pop()
on_stack[w] = False
if w == node:
break
return count
落とし穴と境界ケース
- 辺のないノードを忘れる。2つ目の例では、ノード 4 はどの辺にも含まれていませんが、それでも連結成分です。
- スタック上にあるノードだけでなく、訪問済みの任意のノードを通じて
lowを小さくする。1つ目の例では、辺5 → 4によって、5 が連結成分を確定できなくなります。 - 辺を双方向として扱う。これは連結成分を数えることになり、1つ目の例では 3 ではなく 1 になります。
- Python で再帰する。5000 ノードを通るサイクルでは 5000 回の呼び出しがネストし、デフォルトの上限 1000 の5倍になります。フレームのスタックを自分で管理してください。
- Kosaraju の2回目の走査を元の辺に対して行う、またはノードを最初に訪問した順序で行う。どちらの場合も、一方向にしか到達できない成分が統合されます。
よくある質問3
強連結成分を見つける時間計算量はどれくらいですか？
KosarajuのアルゴリズムまたはTarjanのアルゴリズムでは、各ノードとエッジを定数回処理するため、時間計算量はO(n + E)です。どちらも、エッジリストと探索スタックにO(n + E)の空間を使用します。
Kosaraju法とTarjan法のどちらを使うべきでしょうか？
Kosarajuのアルゴリズムは、単純な探索を2回行うため、間違えにくいです。Tarjanのアルゴリズムは、lowの管理が必要になる代わりに、探索は1回で済み、グラフを反転させる必要もありません。
強連結成分と連結成分の違いは何ですか？
連結成分では辺の向きを無視します。ある経路で結ばれていれば、2つのノードは同じ成分に属します。強連結成分では、それぞれのノードからもう一方のノードへ到達できる必要があります。最初の例は、1つの連結成分ですが、強連結成分は3つあります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def countSCC(n, edges):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
n = 6 edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
期待される出力
3