Cod sursa(job #2787763)

Utilizator Mirc100Mircea Octavian Mirc100 Data 23 octombrie 2021 23:39:01
Problema Parcurgere DFS - componente conexe Scor 65
Compilator py Status done
Runda Arhiva educationala Marime 0.79 kb

def citire(nume_fisier):
    f = open(nume_fisier)
    n, m = [int(x) for x in f.readline().split()]
    l = [[] for i in range(n+1)]
    for linie in f:
    #for i in range(m):
        x, y = [int(a) for a in linie.split()]
        l[x].append(y)
        l[y].append(x)
    f.close()
    return n, l

import sys
sys.setrecursionlimit(100001)




def dfs(x):
    viz[x] = 1
    for y in l[x]:
        if viz[y] == 0:
            dfs(y)





n, l = citire("dfs.in")
y = 0



nrc = 0 #nrc=nr de componente conexe
viz = [0] * (n+1)

for i in range(1,n+1):
    if viz[i]==0: #apelam dfs pentru fiecare varf ramas nevizitat=>o noua componenta conexa
        dfs(i)
        nrc += 1 #creste nr de componente conexe

f = open("dfs.out", "w")
f.write(str(nrc)+"\n")
f.close()