Cod sursa(job #2672647)

Utilizator mirceaisherebina mircea mirceaishere Data 14 noiembrie 2020 12:35:11
Problema Parcurgere DFS - componente conexe Scor 60
Compilator py Status done
Runda Arhiva educationala Marime 0.65 kb
# numarul componentelor conexe

def dfs(nod):
    v[nod] = 1
    for vecin in a[nod]:
        if v[vecin] == 0:
            dfs(vecin)


with open("dfs.in") as fin:
    aux = fin.readline().split()
    n = int(aux[0])
    m = int(aux[1])
    a = []
    v = [0] * (n + 1)
    for i in range(0, n+1):
        a.append([])
    for i in range(m):
        aux = fin.readline().split()
        x = int(aux[0])
        y = int(aux[1])
        a[x].append(y)
        a[y].append(x)

print ("a = ", a)

componente = 0

for i in range(1, n+1):
    if v[i] == 0:
        dfs(i)
        componente += 1

with open("dfs.out", "w") as fout:
    fout.write(str(componente))