Pagini recente » Cod sursa (job #79418) | Cod sursa (job #1494463) | Cod sursa (job #1747241) | Cod sursa (job #939379) | Cod sursa (job #2925585)
f = open("dfs.in")
line = f.readline()
v = line.split()
n = int(v[0])
m = int(v[1])
def citire_matrice_liste(noduri, muchii, orientat):
l = {}
for i in range(1, noduri + 1):
l[i] = []
for i in range(muchii):
line = f.readline()
v = line.split()
if orientat:
l[int(v[0])].append(int(v[1]))
else:
l[int(v[0])].append(int(v[1]))
l[int(v[1])].append(int(v[0]))
return l
lista = citire_matrice_liste(n,m,0)
vizitat = [0] * n
tata = [0] * n
parcurge = []
def DFS(nod):
global vizitat, tata, lista, parcurge
vizitat[nod-1] = 1
# parcurge.append(nod) nu pot sa fac asta pt ca programul e recursiv
for vecin in lista[nod]:
if vizitat[vecin-1] == 0:
DFS(vecin)
def nr_comp():
nr_comp=0
for i in range(n):
if vizitat[i]==0:
nr_comp=nr_comp+1
DFS(i)
return nr_comp
start = 1
DFS(start)
g=open("dfs.out","w")
g.write(nr_comp())