Cod sursa(job #2658560)

Utilizator SmitOanea Smit Andrei Smit Data 14 octombrie 2020 12:47:27
Problema Parcurgere DFS - componente conexe Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 1.29 kb
#avem un graf neorientat

L = []

for i in range(1,100001):
    L.append([])#intial niciun nod nu are vecini
viz = [False] * 100001#o metoda mai simpla de a initializa

with open('dfs.in') as f:
    N, M = [int(x) for x in next(f).split()]#N = numarul de noduri, M = numarul de muchii
    array = []
    for line in f:  # read rest of lines
        linie = [int(x) for x in line.split()]
        x = linie[0]
        y = linie[1]#acum urmeaza sa trasam muchie de la x la y
        L[x].append(y)#il adaug pe y la lista de vecini a lui x
        L[y].append(x)#il adaug pe x la lista de vecini a lui y
        #daca aveam un graf orientat, il adaugam doar pe y la lista lui x, nu si invers

def DFS(x):
    viz[x] = True
    for i in range(len(L[x])):#parcurgem toti vecinii lui x
        y = L[x][i]#y este un vecin al lui x
        if viz[y]==False:
            DFS(y)


#acum numaram cate componente conexe exista
nr_comp_conexe = 0
for i in range(1, N+1):
    if viz[i]==False:#un nod care nu a fost inca "explorat", deci intreaga lui componenta conexa este neexplorata
        nr_comp_conexe+=1
        DFS(i)#acest DFS va marca, in vectorul viz, cu valoarea 1 nodul i, dar si toti vecinii lui, si vecinii vecinilor lui, etc.


#afisam rezultatul
f = open("dfs.out", "w")
f.write((str(nr_comp_conexe) + "\n"))
f.close()