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

    Posted on 2019/06/17

    概要

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

    入力

    %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
    

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