Python初心者 単純連結グラフの橋の数を数えるプログラム

Question

前提・実現したいこと

単純連結グラフの橋の数を数えるプログラム

発生している問題・エラーメッセージ

list index out of range

該当のソースコード

N=7
M=7
edges=((0,2),(1,6),(2,3),(3,4),(3,5),(4,5),(5,6))
sets=[{k} for k in range(N)]
bridge = 0
node_0=0
node_1=0
for m in range(M):
	for j in range(N):
		if edges[m][0] in sets[j]:
			node_0=j
		if edges[m][1] in sets[j]:
			node_1=j
		if node_0 < node_1:
			sets[node_0].update(sets.pop(node_1))
		elif node_0 > node_1:
			sets[node_1].update(sets.pop(node_0))
	if len(sets)>1:
		print( edges[m][0], '->', edges[m][1] )
		bridge = bridge + 1
print( bridge )

試したこと

初心者でどうすれば治るのかわかりません。先人の方たちの教えを請いたいです

Comments

[meg_]

・エラーメッセージは全文掲載してください。
・質問のコードでは何が出力されることを想定していますか？

※「Python初心者」ということは他の言語の経験はあるのでしょうか？

Answer 1

記載のコードによるedgesがわかってるようなので、このedgesの要素数='橋の数'なので、これをカウントするプログラムにしたほうが単純ではないでしょうか？

Answer 2

エラーlist index out of rangeの直接の原因は下記です。

エラーが出る直前のsetsの値は[{0, 2, 3, 4}, {1}, {5}, {6}]で、jの値は5でした。
setsの要素数が4個しかないのにsets[5]にアクセスしようとしてエラーになっています。

setsの要素にアクセスする前に要素数のチェックが必要かと思います。
※質問のコードのアルゴリズムが正しいかどうかは検証していません。

Answer 3

エラーの原因はm=0,j=4の処理が終わった後のsetsが[{0, 2, 3, 4}, {1}, {5}, {6}]になっており、sets[5]が無いためです。