Pagini recente » Cod sursa (job #3231994) | Cod sursa (job #666153) | Borderou de evaluare (job #2783105) | Cod sursa (job #2639177) | Cod sursa (job #2712586)
class FunnyGraph:
def __init__(self):
self.istream = open("dfs.in", "r")
self.ostream = open("dfs.out", "w")
self.visited = set()
self.__read_graph()
self.__build_graph()
self.ostream.write(str(self.__dfs_components(1)))
def __read_graph(self):
self.lines = self.istream.readlines()
self.n, self.m = list(map(int, self.lines[0].strip().split()))
self.lines = self.lines[1:]
print(self.n, self.m)
def __build_graph(self):
self.graph = {}
for i in range(1, self.n+1):
self.graph[i] = []
for line in self.lines:
pair = line.strip().split()
pair = [int(pair[0]), int(pair[1])]
self.graph[pair[0]].append(pair[1])
self.graph[pair[1]].append(pair[0])
print(self.graph)
def __dfs(self, node):
stack = [node]
while len(stack) > 0:
node = stack.pop()
if node in self.visited:
continue
self.visited.add(node)
print("Node: {}".format(node))
for neighbour in self.graph[node]:
if neighbour not in self.visited:
stack.append(neighbour)
def __dfs_components(self, node):
number_of_components = 0
for i in range(1, self.n + 1):
if i not in self.visited:
print("------------------------------------------------------------------")
self.__dfs(i)
print(self.visited)
number_of_components += 1
return number_of_components
FunnyGraph()