Cod sursa(job #470371)

Utilizator stef2nStefan Istrate stef2n Data 13 iulie 2010 15:26:57
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 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')
line = fin.readline()
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):
    line = fin.readline()
    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