Problem:


Score : 100 points

Problem Statement

You are given a directed graph with N vertices and M edges, not necessarily simple. The i-th edge is oriented from the vertex a_i to the vertex b_i.
Divide this graph into strongly connected components and print them in their topological order.

Constraints

1 \leq N \leq 500,000

1 \leq M \leq 500,000

0 \leq a_i, b_i < N

Input

Input is given from Standard Input in the following format:

N M
a_0 b_0
a_1 b_1
:
a_{M - 1} b_{M - 1}

Output

Print 1+K lines, where K is the number of strongly connected components.
Print K on the first line. 
Print the information of each strongly connected component in next K lines in the following format, where l is the number of vertices in the strongly connected component and v_i is the index of the vertex in it.

l v_0 v_1 ... v_{l-1}

Here, for each edge (a_i, b_i), b_i should not appear in earlier line than a_i.

If there are multiple correct output, print any of them.

Sample Input 1

6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2

Sample Output 1

4
1 5
2 4 1
1 2
2 3 0



Sample input:
6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2


Sample output:
4
1 5
2 4 1
1 2
2 3 0

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    from collections import deque

    # compressed[v]: 縮約後のグラフで縮約前のvが属する頂点
    # num: 縮約後のグラフの頂点数
    def SCC(adj, adj_rev):
        N = len(adj) - 1
        seen = [0] * (N + 1)
        compressed = [0] * (N + 1)
        order = []

        for v0 in range(1, N + 1):
            if seen[v0]:
                continue
            st = deque()
            st.append(v0)
            while st:
                v = st.pop()
                if v < 0:
                    order.append(-v)
                else:
                    if seen[v]:
                        continue
                    seen[v] = 1
                    st.append(-v)
                    for u in adj[v]:
                        st.append(u)

        seen = [0] * (N + 1)
        num = 0
        for v0 in reversed(order):
            if seen[v0]:
                continue
            num += 1
            st = deque()
            st.append(v0)
            seen[v0] = 1
            compressed[v0] = num
            while st:
                v = st.pop()
                for u in adj_rev[v]:
                    if seen[u]:
                        continue
                    seen[u] = 1
                    compressed[u] = num
                    st.append(u)

        return num, compressed

    # 縮約後のグラフを構築
    # 先にSCC()を実行してnum, compressedを作っておく
    def construct(adj, num, compressed):
        N = len(adj) - 1
        adj_compressed = [set() for _ in range(num + 1)]
        for v in range(1, N + 1):
            v_cmp = compressed[v]
            for u in adj[v]:
                u_cmp = compressed[u]
                if v_cmp != u_cmp:
                    adj_compressed[v_cmp].add(u_cmp)
        return adj_compressed

    N, M = map(int, input().split())
    adj = [set() for _ in range(N+1)]
    adj_rev = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        adj[a+1].add(b+1)
        adj_rev[b+1].add(a+1)

    num, compressed = SCC(adj, adj_rev)
    ans = [[] for _ in range(num+1)]
    for v in range(1, N+1):
        ans[compressed[v]].append(v-1)
    print(num)
    for i in range(1, num+1):
        line = [len(ans[i])] + ans[i]
        print(*line)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.path.append("/home/contestant/.local/lib/python3.8/site-packages")

import networkx as nx

import io
import os


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
N, M = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(M)]

# Will WA if you don't include nodes with no in/outdegrees
graph = nx.DiGraph()
for i in range(N):
    graph.add_node(i)
for u, v in edges:
    graph.add_edge(u, v)


SCC = list(nx.algorithms.components.strongly_connected_components(graph))
print(len(SCC))
for comp in reversed(SCC):
    print(len(comp), *comp)

Submission status: Accepted

Solution code:
import io
import os


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
N, M = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(M)]

from collections import defaultdict

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v]

# https://atcoder.jp/contests/practice2/submissions/16566401
def scc(G):
    preorder = {}
    lowlink = {}
    seen = [False] * N
    scc_queue = []
    i = 0  # Preorder counter
    ans = []
    for source in range(N):
        if seen[source]:
            continue
        queue = [source]
        while queue:
            v = queue[-1]
            if v not in preorder:
                i = i + 1
                preorder[v] = i
            done = True
            for w in G[v]:
                if w not in preorder:
                    queue.append(w)
                    done = False
                    break
            if done:
                lowlink[v] = preorder[v]
                for w in G[v]:
                    if seen[w]:
                        continue
                    if preorder[w] > preorder[v]:
                        lowlink[v] = min([lowlink[v], lowlink[w]])
                    else:
                        lowlink[v] = min([lowlink[v], preorder[w]])
                queue.pop()
                if lowlink[v] == preorder[v]:
                    scc = {v}
                    seen[v] = True
                    while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
                        k = scc_queue.pop()
                        scc.add(k)
                        seen[k] = True
                    ans.append(scc)
                else:
                    scc_queue.append(v)
    return ans


SCC = list(scc(graph))

DEBUG = False
print(len(SCC))
if DEBUG:
    seen = set()
for comp in reversed(SCC):
    print(len(comp), *comp)
    if DEBUG:
        for u in comp:
            for v in graph[u]:
                assert v not in seen
        seen.update(comp)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
#非再帰
import sys
def scc(Edge):
    N = len(Edge)
    Edgeinv = [[] for _ in range(N)]
    for vn in range(N):
        for vf in Edge[vn]:
            Edgeinv[vf].append(vn)
    
    used = [False]*N
    dim = [len(Edge[i]) for i in range(N)]
    order = []
    for st in range(N):
        if not used[st]:
            stack = [st, 0]
            while stack:
                vn, i = stack[-2], stack[-1]   
                if not i and used[vn]:
                    stack.pop()
                    stack.pop()
                else:
                    used[vn] = True
                    if i < dim[vn]:
                        stack[-1] += 1
                        stack.append(Edge[vn][i])
                        stack.append(0)
                    else:
                        stack.pop()
                        order.append(stack.pop())
    res = [None]*N
    used = [False]*N
    cnt = -1
    for st in order[::-1]:
        if not used[st]:
            cnt += 1
            stack = [st]
            res[st] = cnt
            used[st] = True
            while stack:
                vn = stack.pop()
                for vf in Edgeinv[vn]:
                    if not used[vf]:
                        used[vf] = True
                        res[vf] = cnt
                        stack.append(vf)
    M = cnt+1
    components = [[] for _ in range(M)]
    for i in range(N):
        components[res[i]].append(i)
    tEdge = [[] for _ in range(M)]
    """
    teset = set()
    for vn in range(N):
        tn = res[vn]
        for vf in Edge[vn]:
            tf = res[vf]
            if tn != tf and tn*M + tf not in teset:
                teset.add(tn*M + tf)
                tEdge[tn].append(tf)
    """
    return res, components, tEdge
        
N, M = map(int, readline().split())
Edge = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, readline().split())
    Edge[a].append(b)

R, comp, tE = scc(Edge)
Ans = [str(len(comp))]

for c in comp:
    Ans.append(f'{len(c)} ' + ' '.join(map(str, c)))

print('\n'.join(Ans))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
#非再帰
import sys
def scc(Edge):
    N = len(Edge)
    Edgeinv = [[] for _ in range(N)]
    for vn in range(N):
        for vf in Edge[vn]:
            Edgeinv[vf].append(vn)
    
    used = [False]*N
    dim = [len(Edge[i]) for i in range(N)]
    order = []
    for st in range(N):
        if not used[st]:
            stack = [st, 0]
            while stack:
                vn, i = stack[-2], stack[-1]   
                if not i and used[vn]:
                    stack.pop()
                    stack.pop()
                else:
                    used[vn] = True
                    if i < dim[vn]:
                        stack[-1] += 1
                        stack.append(Edge[vn][i])
                        stack.append(0)
                    else:
                        stack.pop()
                        order.append(stack.pop())
    res = [None]*N
    used = [False]*N
    cnt = -1
    for st in order[::-1]:
        if not used[st]:
            cnt += 1
            stack = [st]
            res[st] = cnt
            used[st] = True
            while stack:
                vn = stack.pop()
                for vf in Edgeinv[vn]:
                    if not used[vf]:
                        used[vf] = True
                        res[vf] = cnt
                        stack.append(vf)
    M = cnt+1
    components = [[] for _ in range(M)]
    for i in range(N):
        components[res[i]].append(i)
    tEdge = [[] for _ in range(M)]
    teset = set()
    for vn in range(N):
        tn = res[vn]
        for vf in Edge[vn]:
            tf = res[vf]
            if tn != tf and tn*M + tf not in teset:
                teset.add(tn*M + tf)
                tEdge[tn].append(tf)
    return res, components, tEdge
        
N, M = map(int, readline().split())
Edge = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, readline().split())
    Edge[a].append(b)

R, comp, tE = scc(Edge)
Ans = [str(len(comp))]

for c in comp:
    Ans.append(f'{len(c)} ' + ' '.join(map(str, c)))

print('\n'.join(Ans))

Submission status: Accepted

Solution code:
from collections import deque

class Graph():  #directed
    def __init__(self, n, edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.rev = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0]].append(e[1])
            self.rev[e[1]].append(e[0])
            self.deg[e[1]] += 1

    def strongry_connected(self):
        group = [None for _ in range(self.n)]
        used = [0 for _ in range(self.n)]
        order = []
        for s in range(self.n):
            if not used[s]:
                stack = [s]
                used[s] = 1
                while stack:
                    node = stack.pop()
                    movable = False
                    for adj in self.graph[node]:
                        if not used[adj]:
                            movable = True
                            used[adj] = 1
                            stack.append(node)
                            stack.append(adj)
                            break
                    if not movable:
                        order.append(node)
        used = [0 for _ in range(self.n)]
        count = 0
        for s in order[::-1]:
            if not used[s]:
                stack = [s]
                group[s] = count
                while stack:
                    node = stack.pop()
                    used[node] = 1
                    for adj in self.rev[node]:
                        if not used[adj]:
                            group[adj] = count
                            stack.append(adj)
                count += 1
        return group, count

    def topological_sort(self):
        res = [i for i in range(self.n) if self.deg[i] == 0]
        queue = deque(res)
        while queue:
            node = queue.popleft()
            for adj in self.graph[node]:
                self.deg[adj] -= 1
                if self.deg[adj] == 0:
                    queue.append(adj)
                    res.append(adj)
        return res

def simplify(edge):
    res = []
    for e in edge:
        if e[0] == e[1]:
            continue
        res.append(e)
    return tuple(set(res))

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]

edge = simplify(edge)

g = Graph(N, edge)
group, count = g.strongry_connected() #node_to_group
group_to_node = [[] for _ in range(count)]

for i in range(N):
    group_to_node[group[i]].append(i)

new_edge = []

for a, b in edge:
    new_edge.append((group[a], group[b]))

new_edge = simplify(new_edge)

new_g = Graph(count, new_edge)
ts = new_g.topological_sort()

res = [[] for _ in range(count)]

for i in range(count):
    res[i].append(len(group_to_node[ts[i]]))
    res[i].extend(group_to_node[ts[i]])

print(count)
print('\n'.join(map(lambda x: ' '.join(map(str, x)), res)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

class SCC:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.graph_rev = [[] for _ in range(n)]
        self.already = [False]*n
    
    def add_edge(self, fr, to):
        if fr == to:
            return
        self.graph[fr].append(to)
        self.graph_rev[to].append(fr)
    
    def dfs(self, node, graph):
        self.already[node] = True
        for n in graph[node]:
            if self.already[n]:
                continue
            self.dfs(n, graph)
        self.order.append(node)
    
    def first_dfs(self):
        self.already = [False]*self.n
        self.order = []
        for i in range(self.n):
            if self.already[i] == False:
                self.dfs(i, self.graph)
    
    def second_dfs(self):
        self.already = [False]*self.n
        self.ans = []
        for n in reversed(self.order):
            if self.already[n]:
                continue
            self.already[n] = True
            self.order = []
            self.dfs(n, self.graph_rev)
            self.order.reverse()
            self.ans.append(self.order)

    def scc(self):
        self.first_dfs()
        self.second_dfs()
        return self.ans


def main():
    n, m = map(int, input().split())
    scc = SCC(n)

    for i in range(m):
        a, b = map(int, input().split())
        scc.add_edge(a, b)
    
    scc_list = scc.scc()

    print(len(scc_list))
    for s in scc_list:
        print(len(s), end=" ")
        print(*s)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

def SCC(N, edges):
    """ 強連結成分分解 """

    nodes1 = [[] for i in range(N)]
    nodes2 = [[] for i in range(N)]
    for u, v in edges:
        nodes1[u].append(v)
        nodes2[v].append(u)

    T = []
    visited = [False] * N
    def rec1(cur):
        visited[cur] = True
        for nxt in nodes1[cur]:
            if not visited[nxt]:
                rec1(nxt)
        T.append(cur)

    for u in range(N):
        if not visited[u]:
            rec1(u)

    visited = [False] * N
    group = [0] * N
    grpnum = 0
    def rec2(cur):
        group[cur] = grpnum
        visited[cur] = True
        for nxt in nodes2[cur]:
            if not visited[nxt]:
                rec2(nxt)

    for u in reversed(T):
        if not visited[u]:
            rec2(u)
            grpnum += 1
    return grpnum, group

N, M = MAP()
edges = []
for i in range(M):
    a, b = MAP()
    edges.append((a, b))

grpnum, group = SCC(N, edges)
ans = [[] for i in range(grpnum)]
for i in range(N):
    ans[group[i]].append(i)

print(grpnum)
for i in range(grpnum):
    ans[i].insert(0, len(ans[i]))
    print(*ans[i])

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8[:, :]), cache=True)
def scc(N, G):
    ind = np.searchsorted(G[:, 0], np.arange(N + 2))
    preorder = np.empty(N, np.int64)
    n = 0
    st = np.empty(N, np.int64)
    p = 0
    nxt = np.full(N + 1, -1, np.int64)

    for root in range(N):
        if nxt[root] != -1:
            continue
        st[p], p = root, p + 1
        while p:
            v = st[p - 1]
            if nxt[v] == -1:
                nxt[v] = ind[v]
            if nxt[v] == ind[v + 1]:
                preorder[n], n = v, n + 1
                p -= 1
                continue
            w = G[nxt[v], 1]
            nxt[v] += 1
            if nxt[w] != -1:
                continue
            st[p], p = w, p + 1
    Grev = G[:, :2][:, ::-1].copy()
    Grev = Grev[np.argsort(Grev[:, 0])]
    ind = np.searchsorted(Grev[:, 0], np.arange(N + 2))
    comp = np.zeros(N, np.int64)
    n_comp = 0
    for root in preorder[::-1]:
        if comp[root]:
            continue
        n_comp += 1
        comp[root] = n_comp
        st[p], p = root, p + 1
        while p:
            v, p = st[p - 1], p - 1
            for i in range(ind[v], ind[v + 1]):
                w = Grev[i, 1]
                if comp[w]:
                    continue
                comp[w] = n_comp
                st[p], p = w, p + 1
    return n_comp, comp

def main(N, G):
    n_comp, comp = scc(N, G)
    ans = np.empty((N, 2), np.int64)
    ans[:, 0] = np.arange(N)
    ans[:, 1] = comp
    ans = ans[np.argsort(ans[:, 1])]
    idx = np.searchsorted(ans[:, 1], np.arange(n_comp + 2))
    print(n_comp)
    for c in range(1, n_comp + 1):
        V = ans[idx[c]:idx[c + 1], 0]
        print(len(V), ' '.join(map(str, V)))

N, M = map(int, readline().split())
AB = np.array(read().split(), np.int64).reshape(-1, 2)

AB = AB[np.argsort(AB[:, 0])]

main(N, AB)

Submission status: Accepted

Solution code:
# verify-helper: PROBLEM https://judge.yosupo.jp/problem/scc
import sys

input = sys.stdin.buffer.readline
sys.setrecursionlimit(6 * 10 ** 5)


class StronglyConnectedComponets:
    def __init__(self, n: int) -> None:
        self.n = n
        self.edges = [[] for _ in range(n)]
        self.rev_edeges = [[] for _ in range(n)]
        self.vs = []
        self.order = [0] * n
        self.used = [False] * n

    def add_edge(self, from_v: int, to_v: int) -> None:
        self.edges[from_v].append(to_v)
        self.rev_edeges[to_v].append(from_v)

    def dfs(self, v: int) -> None:
        self.used[v] = True
        for child in self.edges[v]:
            if not self.used[child]:
                self.dfs(child)
        self.vs.append(v)

    def rdfs(self, v: int, k: int) -> None:
        self.used[v] = True
        self.order[v] = k
        for child in self.rev_edeges[v]:
            if not self.used[child]:
                self.rdfs(child, k)

    def run(self) -> int:
        self.used = [False] * self.n
        self.vs.clear()
        for v in range(self.n):
            if not self.used[v]:
                self.dfs(v)
        self.used = [False] * self.n
        k = 0
        for v in reversed(self.vs):
            if not self.used[v]:
                self.rdfs(v, k)
                k += 1
        return k


def main() -> None:
    N, M = map(int, input().split())
    scc = StronglyConnectedComponets(N)
    for _ in range(M):
        u, v = map(int, input().split())
        scc.add_edge(u, v)
    scc.run()
    ans_size = max(scc.order) + 1
    ans = [[] for _ in range(ans_size)]
    for i, c in enumerate(scc.order):
        ans[c].append(i)
    print(ans_size)
    for row in ans:
        print(len(row), *row)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline


class StronglyConnectedComponents:
    """与えられた有向グラフに対して強連結成分分解する。構築O(N)
    label: 分解されたグラフの個数
    group: 強連結成分のグループ分け番号
    """
    def __init__(self, graph):
        self.n = len(graph)
        self.graph = graph
        self.out_degree = [len(self.graph[i]) for i in range(self.n)]
        self.label = 0
        self.group = [-1] * self.n

        # 逆辺を用いたグラフ(rev_graph)の構築
        self.rev_graph = [[] for i in range(self.n)]
        for a in range(self.n):
            for b in self.graph[a]:
                self.rev_graph[b].append(a)

        # graph上での帰りがけ順(post_order)の構築
        self.post_order = []
        self.used = [False] * self.n
        for v in range(self.n):
            if not self.used[v]:
                self._dfs(v)

        # 帰りがけ順の逆順で走査し、
        # 未訪問かつrev_graph上でたどり着ける頂点は強連結である。
        for v in reversed(self.post_order):
            if self.group[v] == -1:
                self._rev_dfs(v, self.label)
                self.label += 1

    def _dfs(self, v):
        st = [v, 0]
        while st:
            v, ind = st[-2], st[-1]
            if not ind and self.used[v]:
                st.pop()
                st.pop()
            else:
                self.used[v] = True
                if ind < self.out_degree[v]:
                    st[-1] += 1
                    st.append(self.graph[v][ind])
                    st.append(0)
                else:
                    st.pop()
                    self.post_order.append(st.pop())

    def _rev_dfs(self, v, label):
        st = [v]
        self.group[v] = label
        while st:
            v = st.pop()
            for nxt_v in self.rev_graph[v]:
                if self.group[nxt_v] >= 0:
                    continue
                st.append(nxt_v)
                self.group[nxt_v] = label

    def construct(self):
        """縮約グラフ(red_graph)と縮約された頂点が含む元の頂点(red_comps)を
        求める。O(N)
        """
        self.red_graph = [set() for i in range(self.label)]
        self.red_comps = [[] for i in range(self.label)]

        for v in range(self.n):
            lb = self.group[v]
            for nxt_v in self.graph[v]:
                nxt_lb = self.group[nxt_v]
                if lb == nxt_lb:
                    continue
                self.red_graph[lb].add(nxt_lb)
            self.red_comps[lb].append(v)

        return self.red_graph, self.red_comps

    def tp_sort(self):
        """縮約グラフのトポロジカル順を求める。O(N)"""
        red_n = len(self.red_graph)
        indegree = [0] * red_n
        for v in range(red_n):
            for nxt_v in self.red_graph[v]:
                indegree[nxt_v] += 1

        # 入次数 = 0、つまり入力の無い頂点を初期値状態とする。
        tp_order = [i for i in range(red_n) if indegree[i] == 0]
        st = tp_order[:]
        while st:
            v = st.pop()
            for nxt_v in self.red_graph[v]:
                indegree[nxt_v] -= 1
                if indegree[nxt_v] == 0:
                    st.append(nxt_v)
                    tp_order.append(nxt_v)
        return tp_order


n, m = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]


graph = [[] for i in range(n)]
for u, v in edges:
    graph[u].append(v)

scc = StronglyConnectedComponents(graph)
_, red_comps = scc.construct()
tp = scc.tp_sort()

print(len(red_comps))
for v in tp:
    print(len(red_comps[v]), *red_comps[v])

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
ns = [[] for _ in range(n)]
for _ in range(m):
    u,v = map(int, input().split())
    ns[u].append(v)
def scc():
    preorder = {}
    lowlink = {}
    seen = [False]*n
    scc_queue = []
    i = 0  # Preorder counter
    ans = []
    for source in range(n):
        if seen[source]:
            continue
        queue = [source]
        while queue:
            v = queue[-1]
            if v not in preorder:
                i = i + 1
                preorder[v] = i
            done = True
            for w in ns[v]:
                if w not in preorder:
                    queue.append(w)
                    done = False
                    break
            if done:
                lowlink[v] = preorder[v]
                for w in ns[v]:
                    if seen[w]:
                        continue
                    if preorder[w] > preorder[v]:
                        lowlink[v] = min([lowlink[v], lowlink[w]])
                    else:
                        lowlink[v] = min([lowlink[v], preorder[w]])
                queue.pop()
                if lowlink[v] == preorder[v]:
                    scc = {v}
                    seen[v] = True
                    while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
                        k = scc_queue.pop()
                        scc.add(k)
                        seen[k] = True
                    ans.append(scc)
                else:
                    scc_queue.append(v)
    return ans
comp = scc()
print(len(comp))
for item in reversed(comp):
    print(len(item), " ".join(map(str, item)))

Submission status: Runtime Error

Solution code:
import sys


class csr:
    def __init__(self, N, edges):
        self.start = [0]*(N+1)
        self.elist = [0]*len(edges)
        for e in edges:
            self.start[e[0]+1] += 1
        for i in range(1, N+1):
            self.start[i] += self.start[i-1]
        counter = self.start[:]
        for e in edges:
            self.elist[counter[e[0]]] = e[1]
            counter[e[0]] += 1


class scc_graph:
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add_edge(self, v, w):
        self.edges.append((v, w))

    def scc_ids(self):
        N = self.N
        g = csr(N, self.edges)
        now_ord = group_num = 0
        visited = []
        low = [0]*N
        order = [-1]*N
        ids = [0]*N
        stack = []
        for i in range(N):
            if order[i] == -1:
                stack.append(~i)
                stack.append(i)
                while stack:
                    v = stack.pop()
                    if v >= 0:
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        visited.append(v)
                        for i in range(g.start[v], g.start[v+1]):
                            to = g.elist[i]
                            if order[to] == -1:
                                stack.append(~to)
                                stack.append(to)
                                low[v] = min(low[v], low[to])
                            else:
                                low[v] = min(low[v], order[to])
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[u] = N
                                ids[u] = group_num
                                if u == v:
                                    break
                            group_num += 1
        for i, x in enumerate(ids):
            ids[i] = group_num-1-x

        return group_num, ids

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


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

#"""
N, M = map(int, readline().split())
ab = list(map(int, read().split()))
"""
import random
N, M = 500000, 500000
ab = []
vs = list(range(N))
random.shuffle(vs)
for i in range(M):
    ab.append(vs[i])
    ab.append(vs[random.randint(0, i)])
#"""

sg = scc_graph(N)

it = iter(ab)
for a, b in zip(it, it):
    sg.add_edge(a, b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(str(len(group))+' '+' '.join(map(str, group)))

Submission status: Runtime Error

Solution code:
from collections import deque
class csr:
    def __init__(self,N,edges):
        self.start = [0]*(N+1)
        self.elist = [0]*len(edges)
        for e in edges:
            self.start[e[0]+1] += 1
        for i in range(1,N+1):
            self.start[i] += self.start[i-1] 
        counter = self.start[:]
        for e in edges:
            self.elist[counter[e[0]]] = e[1]
            counter[e[0]] += 1

class scc_graph:
    def __init__(self,N):
        self.N = N
        self.edges = []
    
    def add_edge(self,v,w):
        self.edges.append((v,w))

    def scc_ids(self):
        g = csr(self.N,self.edges)
        now_ord = group_num = 0
        visited = deque()
        low = [0]*self.N
        order = [-1]*self.N
        ids = [0]*self.N
        parent = [-1]*self.N
        for i in range(self.N):
            if order[i] == -1:
                stack = deque()
                stack.append(i)
                stack.append(i)
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        visited.append(v)
                        for i in range(g.start[v],g.start[v+1]):
                            to = g.elist[i]
                            if order[to] == -1:
                                stack.append(to)
                                stack.append(to)
                                parent[to] = v
                            else:
                                low[v] = min(low[v],order[to])
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[u] = self.N
                                ids[u] = group_num
                                if u == v:
                                    break
                            group_num += 1
                        if parent[v] != -1:
                            low[parent[v]] = min(low[parent[v]],low[v])
        for i,x in enumerate(ids):
            ids[i] = group_num-1-x

        return group_num,ids
    
    def scc(self):
        group_num,ids = self.scc_ids()
        groups = [[] for _ in range(group_num)]
        for i,x in enumerate(ids):
            groups[x].append(i)
        return groups
    
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
N,M = map(int,readline().split())
ab = list(map(int,read().split()))
sg = scc_graph()

it = iter(ab)
for a,b in zip(it,it):
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(*([len(group)] + group))