Pagini recente » Cod sursa (job #938956) | Cod sursa (job #1409266) | Cod sursa (job #492273) | Cod sursa (job #2579350) | Cod sursa (job #2787759)
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()