GRL_3_C - Strongly Connected Components / PythonでAizu Online Judgeを解く

    Posted on 2019/03/24

    概要

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

    • 行きがけ順を求めるときにリストを反転するのを忘れていました

    サンプル出力