Cod sursa(job #2928241)

Utilizator PatriParaParalescu Flavia-Patricia PatriPara Data 22 octombrie 2022 15:19:02
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.03 kb
f = open("ctc.in", "r")
g = open("ctc.out", "w")
n, m = f.readline().split(' ')
n = int(n)
m = int(m)

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

for linie in f:
    x, y = linie.split(' ')
    x = int(x)
    y = int(y)
    la[x].append(y)
    lat[y].append(x)
f.close()
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
    g.write(f'{str(v)} ')
    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

g.write(f'{str(nr)}\n')

while fin:
    nod =  fin.pop()
    if viz[nod] == 0:
        dfsAfis(nod, viz)
        g.write('\n')