Pagini recente » Cod sursa (job #1392781) | Cod sursa (job #1218292) | Cod sursa (job #2251024) | Cod sursa (job #2140962) | Cod sursa (job #2783086)
class Graph:
def __init__(self, nodes):
self.nodes = nodes
self.neighbours = [[] for _ in range(self.nodes)]
def addUndirectedEdge(self, u, v):
self.neighbours[u].append(v)
self.neighbours[v].append(u)
def dfs(self, node, visited):
visited[node] = True
for i in self.neighbours[node]:
if not visited[i]:
self.dfs(i, visited)
def NumberOfconnectedComponents(self):
visited = [False] * self.nodes
count = 0
for node in range(self.nodes):
if not visited[node]:
self.dfs(node, visited)
count += 1
return count
file = 'dfs.in'
with open(file, 'rt') as f:
content = f.readlines()
content = [line.strip().split() for line in content]
content = [[int(x) for x in line] for line in content]
N, M = content[0][0], content[0][1]
g = Graph(N)
for edges in content[1:]:
g.addUndirectedEdge(edges[0], edges[1])
result = g.NumberOfconnectedComponents()
with open('dfs.out', 'wt') as f:
f.write(str(result))