Cod sursa(job #2925999)

Utilizator bunicul_hackerFlavian bunicul_hacker Data 16 octombrie 2022 15:57:43
Problema Parcurgere DFS - componente conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 0.78 kb
#https://infoarena.ro/problema/dfs

f = open("dfs.in", "r")
g = open("dfs.out", "w")

l = f.readlines()

#scoatem (n,m) si muchiile
l = [x.split() for x in l]
l = [list(map(int, x)) for x in l]

n, m = l[0]
vertices = l[1:]

#intializam culorile varfurilor cu alb
color = ['white' for _ in range(n)]

listaAdiacenta = {x: [] for x in range(1, n + 1)}

for pair in vertices:
    listaAdiacenta[pair[0]].append(pair[1])


#numarul de componente conexe
connectedParts = 0

def DFS(x):
    color[x] = 'grey'
    for vecin in listaAdiacenta[x + 1]: 
        if color[vecin] == 'white':
            DFS(vecin)
        color[x] = 'black'


time = 0
for x in range(n):
    if color[x] == 'white':
        connectedParts += 1
        DFS(x) 

g.write(str(connectedParts))