# Cod sursa(job #470371)

Utilizator Data 13 iulie 2010 15:26:57 Componente tare conexe 0 py done Arhiva educationala 1.09 kb
``````def dfs_time(v):
global used, time, order, current_time, L
used[v] = True
for new_v in L[v]:
if not used[new_v]:
dfs_time(new_v)
time[v] = current_time
order[N - current_time - 1] = v
current_time += 1

def dfs_ctc(v):
global used, partial, RL
used[v] = True
partial.append(v)
for new_v in RL[v]:
if not used[new_v]:
dfs_ctc(new_v)

fin = open('ctc.in', 'r')
N, M = line.split(' ')
N = int(N)
M = int(M)

L = [[] for _ in xrange(N)]
RL = [[] for _ in xrange(N)]

for i in xrange(M):
u, v = line.split(' ')
u = int(u) - 1
v = int(v) - 1
L[u].append(v)
RL[v].append(u)

used = [False] * N
time = [0] * N
current_time = 0
order = [0] * N
for i in xrange(N):
if not used[i]:
dfs_time(i)

result = []
used = [False] * N
for i in xrange(N):
if not used[order[i]]:
partial = []
dfs_ctc(order[i])
result.append(partial)

fout = open('ctc.out', 'w')
print len(result)
for l in result:
for v in l:
print (v + 1),
print
``````