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

Posted on

概要

有向グラフ \(G(V, E)\) について閉路を持つかどうか判定してください

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

入力

%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


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

IndexErrorTraceback (most recent call last)
<ipython-input-19-8850315cd86e> in <module>()
      1 with open('/tmp/input3.txt') as f:
----> 2     solve(*input(f))

<ipython-input-16-4801686e9073> in solve(V, E, s, t)
     20         return 0
     21 
---> 22     print(has_cycle())

<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

<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に辺の本数を渡していました :-|

%md