Cod sursa(job #2787758)

Utilizator Mirc100Mircea Octavian Mirc100 Data 23 octombrie 2021 23:33:24
Problema Parcurgere DFS - componente conexe Scor 60
Compilator py Status done
Runda Arhiva educationala Marime 0.92 kb

def citire(nume_fisier):
    f = open(nume_fisier)
    n, m = [int(x) for x in f.readline().split()]
    l = [[] for i in range(n)]
    for linie in f:
    #for i in range(m):
        x, y = [int(a) for a in linie.split()]
        l[x - 1].append(y - 1) #scazut 1 - lucram cu varfurile numerotate 0,1,...,n-1
        l[y - 1].append(x - 1) #neorientat -se adauga si x in lista vecinilor lui y si invers
    f.close()
    return n, l

#import sys
#sys.setrecursionlimit(100001)




def dfs(x):
    viz[x] = 1
    for y in l[x]:
        if viz[y] == 0:
            dfs(y)





n, l = citire("dfs.in")
y = 0



nrc = 0 #nrc=nr de componente conexe
viz = [0] * n

for i in range(n):
    if viz[i]==0: #apelam dfs pentru fiecare varf ramas nevizitat=>o noua componenta conexa
        dfs(i)
        nrc += 1 #creste nr de componente conexe

f = open("dfs.out", "w")
f.write(str(nrc)+"\n")
f.close()