Cod sursa(job #2293326)

Utilizator MaligMamaliga cu smantana Malig Data 30 noiembrie 2018 20:52:40
Problema Parcurgere DFS - componente conexe Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 0.67 kb
#!/usr/bin/python

def dfs(node, adj, vis):
	vis[node] = True
	for nxt in adj[node]:
		if not vis[nxt]:
			dfs(nxt, adj, vis)

fin = open("dfs.in", "r")
lines = fin.readlines()
fin.close()

N = int(lines[0].replace("\n", " ").split(" ")[0])
M = int(lines[0].replace("\n", " ").split(" ")[1])

adj = {}
vis = {}
for i in range(1, N + 1):
	adj[i] = [];
	vis[i] = False;

for i in range(M):
	x = int(lines[i + 1].replace("\n", " ").split(" ")[0])
	y = int(lines[i + 1].replace("\n", " ").split(" ")[1])

	adj[x].append(y)
	adj[y].append(x)

ans = 0
for i in range(1, N + 1):
	if not vis[i]:
		dfs(i, adj, vis)
		ans += 1

fout = open("dfs.out", "w+")
fout.write(repr(ans))
fout.close()