Pagini recente » Cod sursa (job #632845) | Cod sursa (job #246027) | Cod sursa (job #335512) | Cod sursa (job #1217789) | Cod sursa (job #2797456)
from collections import defaultdict
with open("dfs.in", 'r') as f:
lines = f.readlines()
N, M = [int(val) for val in lines[0].split()]
f.close()
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self, u, v):
self.graph[u].append(v)
def DFS(self, visited, nod_curent):
visited[nod_curent] = True
for i in range(0, len(self.graph[nod_curent])):
if not visited[ self.graph[nod_curent][i] ]:
g.DFS(visited, self.graph[nod_curent][i])
def Componente_Conexe(self):
contor = 0;
visited = [False] * (N+1)
for i in range(1, N+1):
if not visited[i]:
g.DFS(visited, i)
contor += 1
return contor
g = Graph()
for i in range(1, M + 1):
node1, node2 = [int(val) for val in lines[i].split()]
g.addEdge(node1, node2)
g.addEdge(node2, node1)
with open("dfs.out", 'w') as fout:
fout.write('%s ' % g.Componente_Conexe())
fout.close()