Pagini recente » Cod sursa (job #1156601) | Cod sursa (job #297699) | Cod sursa (job #329456) | Cod sursa (job #125421) | Cod sursa (job #2658560)
#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()