Pagini recente » Cod sursa (job #3364004) | Cod sursa (job #3364103) | Cod sursa (job #3364045) | Cod sursa (job #3364102) | Cod sursa (job #3364085)
# 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)