Cod sursa(job #3136195)

Utilizator DavidLDavid Lauran DavidL Data 5 iunie 2023 16:50:38
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 2.99 kb

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()