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
- 行きがけ順を求めるときにリストを反転するのを忘れていました