PythonでAizu Online Judgeを解く/GRL_3_C - Strongly Connected Components
Posted on
概要
有向グラフ \(G(V, E)\) について頂点のペアからなるクエリが \(Q\) 個与えられます。各クエリについて2つの頂点が同じ強連結成分に含まれるかどうか判定してください。
制約
- \(1 \leq |V| \leq 10,000\)
- \(1 \leq |E| \leq 30,000\)
- \(1 \leq Q \leq 100,000\)
強連結成分とは
It is strongly connected, diconnected, or simply strong if it contains a directed path from u to v and a directed path from v to u for every pair of vertices u, v.
https://en.wikipedia.org/wiki/Connectivity_(graph_theory)
有向グラフについて任意の2頂点が到達可能な部分グラフのうち最大となるものを強連結成分と呼びます。
サンプル入力
%sh cat <<EOF > /tmp/input1.txt 5 6 0 1 1 0 1 2 2 4 4 3 3 2 4 0 1 0 3 2 3 3 4 EOF
%python
def input(f):
global V, E, s, t, Q, u, v
V, E = map(int, f.readline().split())
s = [None for _ in range(E)]
t = [None for _ in range(E)]
for i in range(E):
s[i], t[i] = map(int, f.readline().split())
Q = int(f.readline())
u = [None for _ in range(Q)]
v = [None for _ in range(Q)]
for i in range(Q):
u[i], v[i] = map(int, f.readline().split())%python
with open('/tmp/input1.txt') as f:
input(f)
print(V, E)
print(s)
print(t)
print(Q)
print(u)
print(v)(5, 6) [0, 1, 1, 2, 4, 3] [1, 0, 2, 4, 3, 2] 4 [0, 0, 2, 3] [1, 3, 3, 4]
考え方
強連結成分ごとに頂点をグループ分けすることで有向グラフを DAG (Directed Acyclic Graph) という問題解決しやすい形に落とし込むことができます。有向グラフを強連結成分分解するには Kosaraju’s algorithm という方法を用いると効率的に計算することができます。
Kosaraju’s Algorithm
手順は以下の通りです。
- 適当な頂点を起点にDFSで訪れた順序 \(order\) を記録する
- 以下のDFSを \(order\) の順序で起点を変えながら繰り返す
- 辺の向きを反転させてDFSで到達できる頂点は同じ強連結成分に含まれる
- 強連結成分に含まれる2頂点は辺の向きを反転させても互いに到達可能
アニメーション
実装例
%python
import sys
sys.setrecursionlimit(1000000)
def solve():
G = [[] for _ in range(V)]
G_inv = [[] for _ in range(V)]
for i in range(E):
G[s[i]].append(t[i])
G_inv[t[i]].append(s[i])
def find_order():
order = []
used = [False for _ in range(V)]
def rec(cur):
if used[cur]:
return
used[cur] = True
for nxt in G[cur]:
rec(nxt)
order.append(cur)
for i in range(V):
rec(i)
return reversed(order)
def decomp(order):
groups = [None for _ in range(V)]
used = [False for _ in range(V)]
def rec(cur, group_id):
if used[cur]:
return
used[cur] = True
groups[cur] = group_id
for nxt in G_inv[cur]:
rec(nxt, group_id)
group_id = 0
for start in order:
if used[start]:
continue
rec(start, group_id)
group_id += 1
return groups
order = find_order()
groups = decomp(order)
for i in range(Q):
if groups[u[i]] == groups[v[i]]:
print('1')
else:
print('0')サンプル出力
%python
with open('/tmp/input1.txt') as f:
input(f)
solve()1 0 1 1
Wrong Answer #1
%sh curl -s https://judgedat.u-aizu.ac.jp/testcases/GRL_3_C/2/in > /tmp/in2.txt cat /tmp/in2.txt
10 11 0 1 1 2 2 3 3 4 4 5 3 5 5 2 7 8 7 8 8 9 9 8 11 1 2 7 8 0 1 0 2 0 3 7 9 4 6 8 9 3 5 2 5 4 3
- (7, 8) と (7, 9) を誤判定してました
- 入力されたグラフが連結でないケースに対応できてませんでした
%python
with open('/tmp/in2.txt') as f:
input(f)
solve()0 0 0 0 0 0 0 1 1 1 1
Wrong Answer #2
%sh curl https://judgedat.u-aizu.ac.jp/testcases/GRL_3_C/3/in > /tmp/in3.txt cat /tmp/in3.txt
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
100 164 100 164 0 0 125 0 0:00:01 0:00:01 --:--:-- 125
100 164 100 164 0 0 125 0 0:00:01 0:00:01 --:--:-- 125
14 21
0 1
0 2
0 3
1 4
1 5
1 6
2 7
3 8
3 9
4 0
5 4
5 11
6 11
7 8
8 9
8 7
9 10
10 8
11 12
12 13
13 6
14
0 7
0 3
0 6
1 6
2 7
3 13
5 11
0 4
1 5
5 0
7 10
9 7
12 6
13 11
%python
with open('/tmp/in3.txt') as f:
input(f)
solve()0 0 0 0 0 0 0 1 1 1 1 1 1 1
- 行きがけ順を求めるときにリストを反転するのを忘れていました