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ですが、これ自分で思いつけるかってなると難しい感じがします。:-|