Cod sursa(job #2928212)

Utilizator PatriParaParalescu Flavia-Patricia PatriPara Data 22 octombrie 2022 14:24:44
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 0.95 kb
n, m = input().split(' ')
n = int(n)
m = int(m)

la = [[] for i in range(n + 1)] 
lat = [[] for i in range(n + 1)] 

for i in range(0, m):
    x, y = input().split(' ')
    x = int(x)
    y = int(y)
    la[x].append(y)
    lat[y].append(x)

def dfsOrd(v, fin, viz): #dfs + nodurile in ordinea finalizarii
    viz[v] = 1
    for u in la[v]:
        if viz[u] == 0:
            dfsOrd(u, fin, viz)
    fin = fin.append(v) #nodul a fost finalizat

def dfsAfis(v, viz):
    viz[v] = 1
    print(v, end = " ")
    for u in lat[v]:
        if viz[u] == 0:
            dfsAfis(u, viz)

fin = [] #nodurile in ordinea finalizarii din dfs
viz = [0 for i in range(n+1)] #marcam ca nevizitate pt dfs
nr = 1 #nr ctc
for v in range(1, n+1):
    if viz[v] == 0:
        dfsOrd(v, fin, viz)
        nr += 1

viz = [0 for i in range(n+1)] #marcam ca nevizitate pt dfs pt graf transpus

print(nr)

while fin:
    nod =  fin.pop()
    if viz[nod] == 0:
        dfsAfis(nod, viz)
        print("")