PythonでAizu Online Judgeを解く/GRL_3_A - Articulation Points
Posted on
関節点
無向グラフ \(G=(V,E)\) の関節点を列挙してください。
制約
- \(1 \leq |V| \leq 100,000\)
- \(1 \leq |E| \leq 100,000\)
- グラフ \(G\) は連結
- グラフ \(G\) は多重辺をもたない
- グラフ \(G\) は自己ループをもたない
articulationとは
接頭辞の arti- はラテン語の artus (jointの意) から来ているそうです
関節点とは
頂点 \(u\) が関節点 => 連結なグラフ \(G\) について頂点 \(u\) と \(u\) から出ている全ての辺を削除して得られる部分グラフが非連結
サンプル入力
%sh cat <<-EOF > /tmp/input1 4 4 0 1 0 2 1 2 2 3 EOF
%python
def input(f):
global v, e
global s, t
v, e = map(int, f.readline().split())
s = [-1 for _ in range(e)]
t = [-1 for _ in range(e)]
for i in range(e):
s[i], t[i] = map(int, f.readline().split())%python
with open('/tmp/input1') as f:
input(f)
print(v, e)
print(s)
print(t)(4, 4) [0, 0, 1, 2] [1, 2, 2, 3]
考え方
関節点が分かるとネットワーク上のあるノードが消えたときに、それ以外のノードから到達不可能なノードがあるかどうかを判断することができます。
一つの頂点が対象であれば単純にその頂点を無いものとして適当な頂点から到達不可能な頂点があるか調べることができますが、すべての頂点についてそれをやろうとすると \(\mathcal{O}(n^2)\) 程度の計算量になってしまいます。特に今回の問題では入力となるグラフが最大で \(10^5\) 個の頂点を持つので間に合いません。
そこで lowlink と呼ばれる方法を使うと関節点を効率的に列挙することができます。まず適当な頂点を起点に深さ優先探索で未訪問の頂点について訪れた順に連番 ord を割り振り、探索木（DFS-tree）の葉の向きに含まれる頂点か探索時に通らなかった辺が指す頂点に割り当てられた ord の最小値を low[v] とおきます。
このとき探索木について以下の性質が成り立ちます:
- 根が関節点
- 次数が2以上（元のグラフの次数ではない）
- それ以外の頂点 \(u\) が関節点
- \(ord[u] \leq low[v]\) を満たす子 \(v\) が存在
この性質を利用すると関節点の列挙を \(\mathcal{O}(n+m)\) 程度の計算量に抑えることができます。
実装例
%python
import sys
sys.setrecursionlimit(1000000)
def solve():
graph = [[] for _ in range(v)]
for i in range(e):
graph[s[i]].append(t[i])
graph[t[i]].append(s[i])
used = [False for _ in range(v)]
ord = [0 for _ in range(v)]
low = [10**6 for _ in range(v)]
is_articulation = [False for _ in range(v)]
def rec(v, prev, k):
if used[v]:
return
used[v] = True
k = k+1
ord[v] = k
low[v] = ord[v]
cnt = 0
for u in graph[v]:
if not used[u]:
cnt += 1
rec(u, v, k)
low[v] = min(low[v], low[u])
if prev >= 0 and ord[v] <= low[u]:
is_articulation[v] = True
elif u != prev:
low[v] = min(low[v], ord[u])
if prev == -1 and cnt >= 2:
is_articulation[v] = True
return k
rec(0, -1, 0)
for i in range(v):
if is_articulation[i]:
print(i)
solve()Wrong Answer #1: 根の扱いに注意しましょう
%sh cat <<-EOF > /tmp/input2 3 2 0 1 1 2 EOF
%python
with open('/tmp/input2') as f:
input(f)
print(v, e)
print(s)
print(t)(3, 2) [0, 1] [1, 2]
Wrong Answer #2: 無向グラフなことに注意しましょう
%sh cat <<-EOF > /tmp/input3 3 3 0 2 0 1 1 2 EOF
%python
with open('/tmp/input3') as f:
input(f)
print(v, e)
print(s)
print(t)(3, 3) [0, 0, 1] [2, 1, 2]
Wrong Answer #3: Pythonの再帰上限に注意しましょう
%sh curl https://judgedat.u-aizu.ac.jp/testcases/GRL_3_A/34/in > /tmp/input4 head /tmp/input4
% 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:00:01 --:--:-- 0
100 68983 100 68983 0 0 39503 0 0:00:01 0:00:01 --:--:-- 39509
2048 7734
0 29
0 81
0 620
0 669
0 1194
0 1369
0 1442
0 2004
1 52
sys.setrecursionlimit(limit) で上限を変更することができます。
%python
import sys
sys.setrecursionlimit(1000000)
with open('/tmp/input4') as f:
input(f)
solve()95 403 412 423 434 570 622 682 998 1122 1468 1574 1579 1800 1827 1975
参考
- “グラフ探索アルゴリズムとその応用”
- “Pythonの再帰の深さについてあれこれ - 数値計算とかの備忘録（仮）”
雑感
実装してみると何てことはない単純なDFSですが、これ自分で思いつけるかってなると難しい感じがします。:-|
%md