1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
def tarjan(u,root):
if root and not g[u]:
dcc.append([u])
nonlocal t
dfn[u]=low[u]=t=t+1
sk.append(u)
s = 0
for v in g[u]:
if not dfn[v]:
tarjan(v,0)
low[u] = min(low[u],low[v])
if low[v]>=dfn[u]:
s += 1
dcc.append([])
while sk[-1]!=v:
dcc[-1].append(sk.pop())
dcc[-1].extend([sk.pop(),u])
else:
low[u] = min(low[u],dfn[v])
cut[u] = s>root
dfn,low,sk,t = [0]*n,[0]*n,[],0
dcc,cut = [],[0]*n
tarjan(0,1)
|