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

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

サンプル出力