Pagini recente » Cod sursa (job #2339489) | Cod sursa (job #1832422) | Cod sursa (job #3238960) | Cod sursa (job #2213848) | Cod sursa (job #3335536)
problema = "dfs"
f_in = problema + ".in"
f_out = problema + "dfs.out"
adiacenta = {}
vizitati = set()
def dfs(node):
vizitati.add(node)
for vecin in adiacenta[node]:
if vecin not in vizitati:
dfs(vecin)
with open(f_in, "r") as f:
n, m = [int(x) for x in next(f).split()]
for i in range(1,n+1):
adiacenta[i] = []
for l in f:
x, y = [int(a) for a in l.split()]
adiacenta[x].append(y)
adiacenta[y].append(x)
nr_conexe = 0;
for n in adiacenta:
if n not in vizitati:
nr_conexe += 1
dfs(n)
with(open(f_out, "r") as f:
f.write(nr_conexe)
# print(nr_conexe)