Cod sursa(job #2832274)

Utilizator yana25Stan Ana yana25 Data 13 ianuarie 2022 11:55:46
Problema Parcurgere DFS - componente conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 0.7 kb
f = open("dfs.in", "r")

def citireneo():
    d = {}
    s=f.readline().split()
    n = int(s[0])
    m = int(s[1])

    for i in range(1, n + 1):
        d[i] = []

    for i in range(m):
        a = f.readline()
        a = a.split()
        x = int(a[0])
        y = int(a[1])
        d[x].append(y)
        d[y].append(x)
    return d, n


g,n = citireneo()
viz=[0]*n
tata = [0]*n
d = [0]*n

def DFS(x):
    viz[x-1]=1
    for y in g[x]:
        if viz[y-1]==0:
            tata[y-1]=x
            d[y-1]=d[x-1]+1
            DFS(y)

c=0
for i in range(1,n+1):
    if viz[i-1]==0:
        c=c+1
        DFS(i)

ff = open("dfs.out", "a")
ff.write(c)
f.close()
ff.close