Cod sursa(job #2925585)

Utilizator pasare.franci@yahoo.comPasare Francisca [email protected] Data 15 octombrie 2022 19:03:06
Problema Parcurgere DFS - componente conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.02 kb
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())