Cod sursa(job #2928699)

Utilizator melaniaionMelania Ion melaniaion Data 23 octombrie 2022 18:08:54
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.53 kb
#complexitate O(n+m)
def dfs(node):
    global la
    global viz1
    global queue
    if node not in viz1:            #prima parcurgerea DFS pe graful initial
        viz1.append(node)
        queue.append(node)          #retin rezultatul pentru a-l folosi la urmatoarea parcurgere dfs pe graful complementar
        for vecin in la[node]:
                dfs(vecin)

def dfs2(node,ctc):
    global la_reversed
    global viz2                         #parcurg graful complementar in ordine inversa, gasind componentele tare conexe
    if node not in viz2:
        viz2.append(node)
        queue.remove(node)      
        ctc.append(node+1)
        for vecin in la_reversed[node]:
                dfs2(vecin,ctc)

f = open("ctc.in","r")
n,m= (int(x) for x in f.readline().split())
la = [[] for i in range(n)]
la_reversed = [[] for i in range(n)]
for linie in f:
    x,y = (int(a) for a in linie.split())
    la[x-1].append(y-1)                 #lista de adiacenta pentru graful initial
    la_reversed[y-1].append(x-1)        #lista de adiacenta pentru graful complementar
f.close()
viz1 = []
viz2 = []
queue = []
componente = list()
dfs(la[0][0])

while(queue):
    ctc = list()
    dfs2(queue[0],ctc)                      #parcurgere dfs pentru toate nodurile din graful complementar
    componente.append(ctc)                  #retin astfel toate ctc gasite intr-o lista 

with open("ctc.out",'w') as f:
    f.write(str(len(componente))+"\n")
    for i in range(len(componente)):
        f.write(str(componente[i])+"\n")