PythonでAizu Online Judgeを解く/GRL_4_B - Topological Sort

Posted on

概要

DAG であるグラフ \(G (V, E)\) について頂点をトポロジカル順序で出力してください。

URL:
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B

入力

%python
def input(f):
    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())
    return V, E, s, t

制約

  • \(1 \leq |V| \leq 10,000\)
  • \(0 \leq |E| \leq 100,000\)
  • \(G\) は平行辺を持たない
  • \(G\) は自己ループを持たない

サンプル入力

%sh
cat <<EOF > /tmp/input1.txt
6 6
0 1
1 2
3 1
3 4
4 5
5 2
EOF

%python
with open('/tmp/input1.txt') as f:
    print(input(f))
(6, 6, [0, 1, 3, 3, 4, 5], [1, 2, 1, 4, 5, 2])

考え方

トポロジカル順序は頂点間の依存関係を元にしたものでパッケージ管理などで活用することができます。計算については強連結成分分解と同様に各頂点について深さ優先探索で訪れた順に頂点をリストに追加していくことにより \(\mathcal{O}(V+E)\) 程度の計算量に収まります。

実装例

%python
def solve(V, E, s, t):
    graph = [[] for _ in range(V)]
    def add_edge(src, dst):
        graph[src].append(dst)
    for i in range(E):
        add_edge(s[i], t[i])
    
    order = []
    used = [False for _ in range(V)]
    def rec(cur, prev):
        used[cur] = True
        for nxt in graph[cur]:
            if not used[nxt]:
                rec(nxt, cur)
        order.append(cur)
    
    for i in range(V):
        if not used[i]:
            rec(i, -1)
    
    return order

def output(order):
    for v in reversed(order):
        print(v)

サンプル出力

%python
with open('/tmp/input1.txt') as f:
    output(solve(*input(f)))
3
4
5
0
1
2

トポロジカルソートの可視化

%sh
curl -s https://judgedat.u-aizu.ac.jp/testcases/GRL_4_B/15/in > /tmp/input15.txt
head /tmp/input15.txt
20 42
4 19
4 10
4 7
6 2
6 8
6 14
11 12
11 9
11 0


%python
with open('/tmp/input15.txt') as f:
    output(solve(*input(f)))
17
13
11
12
6
14
8
4
2
9
16
5
19
0
10
15
1
18
7
3



良い感じの見せ方が思いつきませんでした :-|