Cod sursa(job #3196764)

Utilizator angifluturFlutur Angelica-Costela angiflutur Data 24 ianuarie 2024 19:07:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator py Status done
Runda Arhiva educationala Marime 1.36 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)


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))