# Cod sursa(job #470400)

Utilizator Data 13 iulie 2010 18:02:39 Componente tare conexe 0 py done Arhiva educationala 1.11 kb
``````#!/usr/bin/env python

def dfs_time(v):
return
global current_time
used[v] = True
for new_v in L[v]:
if not used[new_v]:
dfs_time(new_v)
order[N - current_time - 1] = v
current_time += 1

def dfs_ctc(v):
return
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)

fin.close()

used = [False] * 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')
fout.write(str(len(result)) + '\n')
for l in result:
for v in l:
fout.write(str(v + 1) + ' ')
fout.write('\n')
fout.close()
``````