Cod sursa(job #3364085)

Utilizator antoniogrosuAntonio Grosu antoniogrosu Data 29 august 2026 02:19:30
Problema Parcurgere DFS - componente conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 0.9 kb

# f = open("/Users/codevs/Coding/Facultate/ANUL II/AF/lab2/dfs.in", 'r') 
f = open("dfs.in", 'r')
w = open("dfs.out", 'w') 
 


lines = f.read()

lines = lines.strip()
lines = lines.split('\n')


n, m = lines[0].split()
n = int(n)
m = int(m)

lines = [lines[i] for i in range(1, m + 1)]

graf = [[] for i in range(n + 1)] 

for line in lines:
    line = line.strip()
    a, b = line.split()
    a = int(a)
    b = int(b)
    graf[a].append(b)
    graf[b].append(a)  




def dfs(graf, start):
    viz = set()
    ordine = []
    def go(u):
        viz.add(u)
        ordine.append(u)
        for v in graf[u]:
            if v not in viz:
                go(v)
    go(start)
    return ordine
    


viz_global = []
conex = 0
for i in range(1,n+1):
    if i not in viz_global:
        conex +=1
        ord = dfs(graf, i)
        for num in ord:
            viz_global.append(num)
            
# print(conex)
w.write(conex)