Cod sursa(job #2928645)

Utilizator sosig132Munteanu Andre sosig132 Data 23 octombrie 2022 16:07:03
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.37 kb
from collections import defaultdict
import sys
sys.setrecursionlimit(30000)

def DFSfirst(node):
    viz[node]=1
    
    for neigh in graph[node]:
        if viz[neigh]==0:
            DFSfirst(neigh)

    stack.append(node)

def reverseGraph(graph):
    revGraph = defaultdict(list)

    for i in graph.keys():
        for j in graph[i]:
            revGraph[j].append(i)
    return revGraph

def DFSsecond(node):
    
    viz2[node]=1
    
    rezlist[rez].append(node)

    for neigh in revGraph[node]:
        if viz2[neigh]==0:
            DFSsecond(neigh)


stack = []


graph = defaultdict(list)

with open("ctc.in") as file:
    n, m = [int(x) for x in file.readline().split(" ")]
    for _ in range(m):
        a, b = [int(x) for x in file.readline().split(" ")]
        graph[a].append(b)

viz = [0 for x in range(n+1)]
viz2 = [0 for x in range(n+1)]
for node in range(1,n+1):    
    if viz[node]==0:
        DFSfirst(node)

revGraph = reverseGraph(graph)

rez=0

rezlist = defaultdict(list)

while stack!=[]:
    x = stack.pop()

    if viz2[x]==0:
        DFSsecond(x)
        rez+=1
for i in rezlist.keys():
    rezlist[i].sort()

with open('ctc.out', 'w') as file:
    file.write(str(rez,))
    file.write('\n')
    for i in rezlist:
        
        file.write(' '.join(map(str,rezlist[i])))
        file.write('\n')