PythonでAizu Online Judgeを解く/GRL_4_A - Cycle Detection for a Directed Graph
Posted on
概要
有向グラフ \(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
%python with open('/tmp/input3.txt') as f: solve(*input(f))
[0;31m[0m [0;31mIndexError[0mTraceback (most recent call last) [0;32m<ipython-input-19-8850315cd86e>[0m in [0;36m<module>[0;34m()[0m [1;32m 1[0m [0;32mwith[0m [0mopen[0m[0;34m([0m[0;34m'/tmp/input3.txt'[0m[0;34m)[0m [0;32mas[0m [0mf[0m[0;34m:[0m[0;34m[0m[0m [0;32m----> 2[0;31m [0msolve[0m[0;34m([0m[0;34m*[0m[0minput[0m[0;34m([0m[0mf[0m[0;34m)[0m[0;34m)[0m[0;34m[0m[0m [0m [0;32m<ipython-input-16-4801686e9073>[0m in [0;36msolve[0;34m(V, E, s, t)[0m [1;32m 20[0m [0;32mreturn[0m [0;36m0[0m[0;34m[0m[0m [1;32m 21[0m [0;34m[0m[0m [0;32m---> 22[0;31m [0;32mprint[0m[0;34m([0m[0mhas_cycle[0m[0;34m([0m[0;34m)[0m[0;34m)[0m[0;34m[0m[0m [0m [0;32m<ipython-input-16-4801686e9073>[0m in [0;36mhas_cycle[0;34m()[0m [1;32m 16[0m [0;32mdef[0m [0mhas_cycle[0m[0;34m([0m[0;34m)[0m[0;34m:[0m[0;34m[0m[0m [1;32m 17[0m [0;32mfor[0m [0mi[0m [0;32min[0m [0mrange[0m[0;34m([0m[0mE[0m[0;34m)[0m[0;34m:[0m[0;34m[0m[0m [0;32m---> 18[0;31m [0;32mif[0m [0mdist[0m[0;34m[[0m[0mi[0m[0;34m][0m[0;34m[[0m[0mi[0m[0;34m][0m [0;34m!=[0m [0minf[0m[0;34m:[0m[0;34m[0m[0m [0m[1;32m 19[0m [0;32mreturn[0m [0;36m1[0m[0;34m[0m[0m [1;32m 20[0m [0;32mreturn[0m [0;36m0[0m[0;34m[0m[0m [0;31mIndexError[0m: 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