Pagini recente » Cod sursa (job #2965011) | Cod sursa (job #923276) | Cod sursa (job #2629982) | Cod sursa (job #501094) | Cod sursa (job #2787758)
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()