Pagini recente » Cod sursa (job #979120) | Cod sursa (job #869414) | Cod sursa (job #242413) | Borderou de evaluare (job #2199123) | Cod sursa (job #2533356)
import math, queue
def read_gen(fname):
with open(fname, 'rt') as fin:
for line in fin:
for val in line.split():
yield int(val)
def dfs(x, g, used):
used[x] = True
for node in g[x]:
if used[node] == False:
dfs(node, g, used)
def solve(n, g):
cnt_comp = 0
used = {x: False for x in range(1, n + 1)}
for i in range(1, n + 1):
if used[i] is False:
cnt_comp += 1
dfs(i, g, used)
return cnt_comp
if __name__ == "__main__":
it = read_gen('dfs.in')
n, m = next(it), next(it)
g = {x: [] for x in range(1, n + 1)}
for _ in range(m):
x, y = next(it), next(it)
g[x].append(y)
g[y].append(x)
cnt_comp = solve(n, g)
with open('dfs.out', 'wt') as fout:
fout.write('{}\n'.format(cnt_comp))