scc

強連結成分分解をします

冒頭にある

import sys
sys.setrecursionlimit(10**6)

が無いと再帰制限に引っかかってREの原因となります。必要に応じて数字を10**6から変えてください。

追記：2022年2月22日のアップデートにより、非再帰バージョンに変更されました。よって以降のバージョンではsetrecursionlimitは必要ありません。

使用例

(https://atcoder.jp/contests/practice2/tasks/practice2_g)

def scc(N,edges):
    # (中略)
N,M=map(int,input().split())
edges=[]
for i in range(M):
    a,b=map(int,input().split())
    edges.append((a,b))
ans=scc(N,edges)
print(len(ans))
for line in ans:
    print(*([len(line)]+line))

関数の呼び出しは、(N,edges)となっています。 ここで、Nはグラフの頂点の数であり、edgesは辺のリストとなっています。 edgesはリストの構造を持っており、リストの各要素は2次元のタプルでなければいけません。 具体的に,edgesの要素数はM(=辺の数)であり、各要素は(i,j)というタプルになっています。 ここで、(i,j)というのは、i->jへの辺があるという意味になります。 sccの返り値は2次元のリストとなっています。 全体のリストの要素数は強連結成分の数だけあって、各リストの要素は強連結成分に含まれる頂点すべてが入っています。