Pagini recente » Cod sursa (job #200417) | Cod sursa (job #1984769) | Cod sursa (job #1596498) | Cod sursa (job #200439) | Cod sursa (job #3136195)
class DirectedGraph:
def __init__(self, n):
self.__n = n
self.__neigh_in = [[] for _ in range(n + 1)]
self.__neigh_out = [[] for _ in range(n + 1)]
def get_number_vertices(self):
return self.__n
def parse_vertices(self):
return [x for x in range(1, self.__n + 1)]
def parse_in(self, vertex):
return list(self.__neigh_in[vertex])
def parse_out(self, vertex):
return list(self.__neigh_out[vertex])
def add_edge(self, a, b):
self.__neigh_out[a].append(b)
self.__neigh_in[b].append(a)
#
# def print_tree_nicely(parent, vertex, no_tabs):
# for _ in range(no_tabs):
# print(" ", end='')
# print(vertex)
#
# for child in range(1, len(parent)): # ugly ugly
# if parent[child] == vertex:
# print_tree_nicely(parent, child, no_tabs + 1)
#
def read():
fin = open("ctc.in")
n, m = fin.readline().split()
n = int(n)
m = int(m)
graph = DirectedGraph(n)
inv_graph = DirectedGraph(n)
for _ in range(m):
a, b = fin.readline().split()
a = int(a)
b = int(b)
graph.add_edge(a, b)
inv_graph.add_edge(b, a)
fin.close()
return graph, inv_graph
def dfs_order(graph: DirectedGraph, vertex, order: list, visited: list):
visited[vertex] = True
for neighbor in graph.parse_out(vertex):
if not visited[neighbor]:
dfs_order(graph, neighbor, order, visited)
order.append(vertex)
def bfs_main(graph: DirectedGraph, vertex, his_comp: list):
curr_comp = his_comp[vertex]
q = []
q.append(vertex)
while len(q):
curr_vertex = q[0]
q = q[1:]
for neighbor in graph.parse_out(curr_vertex):
if his_comp[neighbor] == -1:
his_comp[neighbor] = curr_comp
q.append(neighbor)
if __name__ == '__main__':
graph, inv_graph = read()
n = graph.get_number_vertices()
# 1. determine the order to pass the vertices (use the inverse graph)
order = []
visited = [False] * (n + 1)
for vertex in graph.parse_vertices():
if not visited[vertex]:
dfs_order(inv_graph, vertex, order, visited)
order.reverse()
# 2. simple dfs/bfs in that order (use the original graph)
his_comp = [-1] * (n + 1)
no_comp = 0
for vertex in order:
if his_comp[vertex] == -1:
no_comp += 1
his_comp[vertex] = no_comp
bfs_main(graph, vertex, his_comp)
in_that_comp = dict()
for comp in range(1, no_comp + 1):
in_that_comp[comp] = []
for vertex in graph.parse_vertices():
in_that_comp[his_comp[vertex]].append(vertex)
fout = open("ctc.out", "w")
fout.write(str(no_comp) + "\n")
for comp in range(1, no_comp + 1):
for vertex in in_that_comp[comp]:
fout.write(str(vertex) + " ")
fout.write("\n")
fout.close()