Pagini recente » Cod sursa (job #1938698) | Cod sursa (job #2302832) | Cod sursa (job #1503516) | Cod sursa (job #1919725) | Cod sursa (job #2449729)
#!/usr/bin/env python3
import sys
sys.stdout = open('ctc.out', 'w')
class Node(object):
def __init__(self, lbl):
self.lbl = lbl
self.onStack = False
self.idx = None
self.minIdx = None
self.edges = []
with open('ctc.in', 'r') as f:
pair = lambda: tuple(map(int, f.readline().split()))
N, M = pair()
nodes = [Node(str(i + 1)) for i in range(N)]
for _ in range(M):
A, B = pair()
nodes[A - 1].edges.append(nodes[B - 1])
idx, stk, solStk, ctc = 0, [], [], []
def dfs(v):
global idx
v.idx = v.minIdx = idx
idx += 1
stk.append(v)
solStk.append(v)
v.onStack = True
while stk:
v = stk[-1]
while v.edges:
vv = v.edges.pop()
if vv.idx is None:
vv.idx = vv.minIdx = idx
idx += 1
stk.append(vv)
solStk.append(vv)
vv.onStack = True
break
elif vv.onStack:
v.minIdx = min(v.minIdx, vv.idx)
if v == stk[-1]:
v = stk.pop()
if stk:
stk[-1].minIdx = min(stk[-1].minIdx, v.minIdx)
if v.idx == v.minIdx:
s = []
while True:
vv = solStk.pop()
vv.onStack = False
s.append(vv.lbl)
if vv == v:
break
ctc.append(' '.join(s))
for v in nodes:
if v.idx is None: dfs(v)
print(len(ctc))
for x in ctc:
print(x)