Pagini recente » Cod sursa (job #2517922) | Cod sursa (job #2950523) | clasament-arhiva-monthly | Cod sursa (job #1132210) | Cod sursa (job #2925999)
#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))