GRL_3_A - Articulation Points / PythonでAizu Online Judgeを解く

Posted on 2019/03/12

関節点

無向グラフ \(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

参考

雑感

実装してみると何てことはない単純なDFSですが、これ自分で思いつけるかってなると難しい感じがします。:-|