Pagini recente » Cod sursa (job #3252076) | Cod sursa (job #2258736) | Cod sursa (job #3225725) | Cod sursa (job #783391) | Cod sursa (job #3196764)
def citire(orientat):
with open("dfs.in", "r") as f:
n, m = map(int, f.readline().split())
muchii = [tuple(map(int, line.split())) for line in f]
liste_adiacenta = {i: [] for i in range(1, n + 1)}
for nod1, nod2 in muchii:
liste_adiacenta[nod1].append(nod2)
if not orientat:
liste_adiacenta[nod2].append(nod1)
return n, m, liste_adiacenta
def afiseaza_liste_adiacenta():
print("Listele de adiacență:")
for nod, vecini in liste_adiacenta.items():
print(f"{nod}: {', '.join(map(str, vecini))}")
def dfs(x):
viz[x] = 1
# print(x, end=" ")
for y in liste_adiacenta[x]:
if viz[y] == 0:
tata[y] = x
dfs(y)
def dfs_iterativ(start):
stack = [start]
viz[start] = 1
while stack:
nod = stack.pop()
# procesați nodul aici (dacă este necesar)
for vecin in liste_adiacenta[nod]:
if viz[vecin] == 0:
viz[vecin] = 1
stack.append(vecin)
n, m, liste_adiacenta = citire(False) #True = orientat, False = neorientat
viz=[0]*(n+1)
tata=[-1]*(n+1)
d=[-1]*(n+1)
nr_componente = 0
for nod in range(1, n+1):
if viz[nod] == 0:
nr_componente += 1
dfs_iterativ(nod)
with open("dfs.out", "w") as g:
g.write(str(nr_componente))