Pagini recente » Cod sursa (job #2909731) | Cod sursa (job #2788820)
class Node:
def __init__(self, val):
self.val = val
self.edges = []
class Graph:
def __init__(self, nodes=None):
if nodes is None:
nodes = []
self.nodes = nodes
def add_node(self, val):
new_node = Node(val)
self.nodes.append(new_node)
def add_edge(self, node1, node2):
node1.edges.append(node2)
node2.edges.append(node1)
def dfs(self, starting_node):
if not self.nodes:
return []
start = self.nodes[starting_node-1]
visited, stack, result = {start}, [start], []
while stack:
node = stack.pop()
result.append(node)
for n in node.edges:
if n not in visited:
stack.append(n)
visited.add(n)
return result
graph = Graph()
f = open("dfs.in", "r")
f_out = open("dfs.out", "w")
N, M = [int(x) for x in f.readline().split()]
for i in range(1, N + 1):
graph.add_node(i)
for i in range(M):
x, y = [int(z) for z in f.readline().split()]
for n0 in graph.nodes:
for n1 in graph.nodes:
if n0.val == x and n1.val == y:
graph.add_edge(n0, n1)
break
connected = set()
node = [z for z in range(1, N + 1)]
for component in node:
dfs_result = graph.dfs(component)
connected.add(tuple(dfs_result))
for j in range(len(dfs_result)):
node.remove(dfs_result[j].val)
f_out.write(str(len(connected)+len(node)))