Submission #31323318

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
def csr(n, E):
    start = [0] * (n + 1)
    elist = [0] * len(E)
    for e in E:
        start[e[0] + 1] += 1
    for i in range(1, n + 1):
        start[i] += start[i - 1]
    counter = start[:]
    for e0, e1 in E:
        elist[counter[e0]] = e1
        counter[e0] += 1
    return start, elist
class SCC_graph:
    def __init__(self, n):
        self._n = n
        self.edges = []
        sys.setrecursionlimit(max(2*n, sys.getrecursionlimit()))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys


def csr(n, E):
    start = [0] * (n + 1)
    elist = [0] * len(E)
    for e in E:
        start[e[0] + 1] += 1
    for i in range(1, n + 1):
        start[i] += start[i - 1]
    counter = start[:]
    for e0, e1 in E:
        elist[counter[e0]] = e1
        counter[e0] += 1
    return start, elist

class SCC_graph:
    def __init__(self, n):
        self._n = n
        self.edges = []
        sys.setrecursionlimit(max(2*n, sys.getrecursionlimit()))

    def num_vertices(self):
        return self._n

    def add_edge(self, frm, to):
        self.edges.append([frm, to])

    def scc_ids(self):
        start, elist = csr(self._n, self.edges)
        now_ord, group_num = 0, 0
        visited = []
        low = [0] * self._n
        ord_ = [-1] * self._n
        ids = [0] * self._n
        def dfs(v):
            nonlocal now_ord, group_num, visited, low, ord_, ids
            low[v] = ord_[v] = now_ord
            now_ord += 1
            visited.append(v)
            for i in range(start[v], start[v+1]):
                to = elist[i]
                if ord_[to] == -1:
                    dfs(to)
                    if low[to] < low[v]: low[v] = low[to]
                else:
                    if ord_[to] < low[v]: low[v] = ord_[to]
            if low[v] == ord_[v]:
                while True:
                    u = visited.pop()
                    ord_[u] = self._n
                    ids[u] = group_num
                    if u == v: break
                group_num += 1
    
        for i in range(self._n):
            if ord_[i] == -1: dfs(i)
        for i in range(self._n):
            ids[i] = group_num - 1 - ids[i]
    
        return group_num, ids

    def scc(self):
        group_num, ids = self.scc_ids()
        groups = [[] for _ in range(group_num)]
        for i in range(self._n):
            groups[ids[i]].append(i)
        return groups

def main():
    n, m = map(int, input().split())
    scc_graph = SCC_graph(n)
    for _ in range(m):
        a, b = map(int, input().split())
        scc_graph.add_edge(a, b)

    groups = scc_graph.scc()
    n_scc = len(groups)
    print(n_scc)
    for i in range(n_scc):
        g = groups[i]
        print(len(g), ' '.join(map(str, g)))



if __name__ == '__main__':
    main()

Submission Info

Judge Result