GRL_4_A - Cycle Detection for a Directed Graph / PythonでAizu Online Judgeを解く

    Posted on 2019/03/30

    概要

    有向グラフ \(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 100\)
    • \(0 \leq |E| \leq 1,000\)
    • \(s_i \neq t_i\)

    サンプル入力 #1

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

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

    考え方

    入力となる有向グラフが閉路を持つとき自分自身に戻ってくることができるような経路が存在します。つまり自分自身への最短距離を求めることができるような頂点が存在すればグラフは閉路を持ちます。

    ここでは頂点の数が最大で100個と少ないので辺の重みを 1 としてワーシャル・フロイド法を適用することで \(\mathcal{O}(n^3)\) 程度の計算量で閉路を検出することができます。

    実装例

    %python
    import sys
    
    def solve(V, E, s, t):
        inf = sys.maxint
        dist = [[inf for _ in range(V)] for _ in range(V)]
        
        for i in range(E):
            dist[s[i]][t[i]] = 1
        
        for k in range(V):
            for i in range(V):
                for j in range(V):
                    if i != k and k != j and dist[i][k] != inf and dist[k][j] != inf:
                            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        
        def has_cycle():
            for i in range(V):
                if dist[i][i] != inf:
                    return 1
            return 0
        
        print(has_cycle())

    サンプル入力 #1 の出力

    %python
    with open('/tmp/input1.txt') as f:
        solve(*input(f))
    0
    

    閉路を持たないケースです

    サンプル入力 #2

    %sh
    cat <<EOF > /tmp/input2.txt
    3 3
    0 1
    1 2
    2 0
    EOF

    %python
    with open('/tmp/input2.txt') as f:
        solve(*input(f))
    1
    

    入力されたグラフが閉路を持つケースです

    Wrong Answer #1: ランタイムエラー

    %sh
    curl -s https://judgedat.u-aizu.ac.jp/testcases/GRL_4_A/3/in > /tmp/input3.txt
    cat /tmp/input3.txt
    5 6
    0 1
    0 2
    0 3
    1 4
    2 4
    4 3
    

    <ipython-input-16-4801686e9073> in has_cycle()
         16     def has_cycle():
         17         for i in range(E):
    ---> 18             if dist[i][i] != inf:
         19                 return 1
         20         return 0
    
    IndexError: list index out of range
    

    閉路検出時のrangeに辺の本数を渡していました :-|