Cod sursa(job #3196756)

Utilizator angifluturFlutur Angelica-Costela angiflutur Data 24 ianuarie 2024 18:56:23
Problema Parcurgere DFS - componente conexe Scor 60
Compilator py Status done
Runda Arhiva educationala Marime 1.04 kb
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)

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(nod)
with open("dfs.out", "w") as g:
    g.write(str(nr_componente))