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

Solution (Python):
import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
readlines=sys.stdin.buffer.readlines

def scc(g):
    n=len(g)
    cmp=[0]*n
    ord=[-1]*n
    fin=[False]*n
    low=[0]*n
    visited=[]
    num=0
    k=0
    for x in range(n):
        if ord[x]!=-1:
            continue
        st=[~x, x]
        while st:
            v=st.pop()
            if v>=0:
                if ord[v]!=-1:
                    continue
                ord[v]=num
                low[v]=num
                num+=1
                visited.append(v)
                for w in g[v]:
                    if ord[w]==-1:
                        st.append(~w)
                        st.append(w)
            else:
                v=~v
                if fin[v]:
                    continue
                fin[v]=True
                for w in g[v]:
                    if ord[w]<ord[v]:
                        if ord[w]<low[v]:
                            low[v]=ord[w]
                    elif ord[w]<n:
                        if low[w]<low[v]:
                            low[v]=low[w]
                if ord[v]==low[v]:
                    while True:
                        w=visited.pop()
                        cmp[w]=k
                        ord[w]=n
                        if w==v:
                            break
                    k+=1
    cmp=[k-1-x for x in cmp]
    return (k, cmp)
n, m=map(int, readline().split())
g=[[] for _ in range(n)]
ab=map(int, read().split())
for a, b in zip(ab, ab):
    g[a].append(b)
k, cmp=scc(g)
print(k)
vs=[[] for _ in range(k)]
ans=[]
for i, x in enumerate(cmp):
    vs[x].append(i)
for v in vs:
    ans.append(f"{len(v)} "+" ".join(map(str, v)))
print("\n".join(ans))

Solution (Python):
import types

_atcoder_code = """


__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder__scc_code = """
import copy
import sys
import typing


class CSR:
    def __init__(
            self, n: int, edges: typing.List[typing.Tuple[int, int]]) -> None:
        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 = copy.deepcopy(self.start)
        for e in edges:
            self.elist[counter[e[0]]] = e[1]
            counter[e[0]] += 1


class SCCGraph:
    '''
    Reference:
    R. Tarjan,
    Depth-First Search and Linear Graph Algorithms
    '''

    def __init__(self, n: int) -> None:
        self._n = n
        self._edges = []

    def num_vertices(self) -> int:
        return self._n

    def add_edge(self, from_vertex: int, to_vertex: int) -> None:
        self._edges.append((from_vertex, to_vertex))

    def scc_ids(self) -> typing.Tuple[int, typing.List[int]]:
        g = CSR(self._n, self._edges)
        now_ord = 0
        group_num = 0
        visited = []
        low = [0] * self._n
        order = [-1] * self._n
        ids = [0] * self._n

        sys.setrecursionlimit(max(self._n + 1000, sys.getrecursionlimit()))

        def dfs(v: int) -> None:
            nonlocal now_ord
            nonlocal group_num
            nonlocal visited
            nonlocal low
            nonlocal order
            nonlocal ids

            low[v] = now_ord
            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:
                    dfs(to)
                    low[v] = min(low[v], low[to])
                else:
                    low[v] = min(low[v], order[to])

            if low[v] == order[v]:
                while True:
                    u = visited[-1]
                    visited.pop()
                    order[u] = self._n
                    ids[u] = group_num
                    if u == v:
                        break
                group_num += 1

        for i in range(self._n):
            if order[i] == -1:
                dfs(i)

        for i in range(self._n):
            ids[i] = group_num - 1 - ids[i]

        return group_num, ids

    def scc(self) -> typing.List[typing.List[int]]:
        ids = self.scc_ids()
        group_num = ids[0]
        counts = [0] * group_num
        for x in ids[1]:
            counts[x] += 1
        groups = [[] for _ in range(group_num)]
        for i in range(self._n):
            groups[ids[1][i]].append(i)

        return groups
"""

atcoder._scc = types.ModuleType('atcoder._scc')
exec(_atcoder__scc_code, atcoder._scc.__dict__)


_atcoder_scc_code = """
import typing




class SCCGraph:
    def __init__(self, n: int = 0) -> None:
        self._internal = atcoder._scc.SCCGraph(n)

    def add_edge(self, from_vertex: int, to_vertex: int) -> None:
        n = self._internal.num_vertices()
        assert 0 <= from_vertex < n
        assert 0 <= to_vertex < n
        self._internal.add_edge(from_vertex, to_vertex)

    def scc(self) -> typing.List[typing.List[int]]:
        return self._internal.scc()
"""

atcoder.scc = types.ModuleType('atcoder.scc')
exec(_atcoder_scc_code, atcoder.scc.__dict__)
atcoder.scc.__dict__['atcoder'] = atcoder
atcoder.scc.__dict__['atcoder._scc'] = atcoder._scc
SCCGraph = atcoder.scc.SCCGraph



import sys




def main() -> None:
    n, m = map(int, sys.stdin.readline().split())
    g = SCCGraph(n)

    for i in range(m):
        u, v = map(int, sys.stdin.readline().split())
        g.add_edge(u, v)

    scc = g.scc()

    print(len(scc))
    for v in scc:
        print(len(v), end='')
        for x in v:
            print(f' {x}', end='')
        print('')


if __name__ == '__main__':
    main()

Solution (Python):
"""
scc の計算自体は 300～400ms程度。
あとは import と出力"""

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[:, :], i8[:], i8[:], i8[:], i8[:], i8[:], i8, i8, i8, i8),
      cache=True)
def scc_dfs(N, G, idx, low, ord, ids, visited, now_ord, group_num, vis_i, v):
    low[v] = ord[v] = now_ord
    now_ord += 1
    visited[vis_i], vis_i = v, vis_i + 1
    for e in range(idx[v], idx[v + 1]):
        to = G[e, 1]
        if ord[to] == -1:
            now_ord, group_num, vis_i = \
                scc_dfs(N, G, idx, low, ord, ids,
                        visited, now_ord, group_num,
                        vis_i, to)
            low[v] = min(low[v], low[to])
        else:
            low[v] = min(low[v], ord[to])
    if low[v] == ord[v]:
        while True:
            u, vis_i = visited[vis_i - 1], vis_i - 1
            ord[u] = N
            ids[u] = group_num
            if u == v:
                break
        group_num += 1
    return now_ord, group_num, vis_i


@njit((i8, i8[:, :]), cache=True)
def scc(N, G):
    idx = np.searchsorted(G[:, 0], np.arange(N + 1))
    low = np.zeros(N, np.int64)
    ord = np.zeros(N, np.int64) - 1
    now_ord = 0
    group_num = 0
    visited, vis_i = np.empty(N, np.int64), 0
    ids = np.zeros(N, np.int64)
    for v in range(N):
        if ord[v] == -1:
            now_ord, group_num, vis_i = \
                scc_dfs(N, G, idx, low, ord, ids,
                        visited, now_ord, group_num,
                        vis_i, v)
    return group_num, group_num - ids - 1

@njit((i8, i8[:, :]), cache=True)
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 + 1))
    print(n_comp)
    for c in range(n_comp):
        V = ans[idx[c]:idx[c + 1], 0]
        print(len(V))
        for v in V:
            print(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)

Solution (Python):
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[:, :], i8[:], i8[:], i8[:], i8[:], i8[:], i8, i8, i8, i8),
      cache=True)
def scc_dfs(N, G, idx, low, ord, ids, visited, now_ord, group_num, vis_i, v):
    low[v] = ord[v] = now_ord
    now_ord += 1
    visited[vis_i], vis_i = v, vis_i + 1
    for e in range(idx[v], idx[v + 1]):
        to = G[e, 1]
        if ord[to] == -1:
            now_ord, group_num, vis_i = \
                scc_dfs(N, G, idx, low, ord, ids,
                        visited, now_ord, group_num,
                        vis_i, to)
            low[v] = min(low[v], low[to])
        else:
            low[v] = min(low[v], ord[to])
    if low[v] == ord[v]:
        while True:
            u, vis_i = visited[vis_i - 1], vis_i - 1
            ord[u] = N
            ids[u] = group_num
            if u == v:
                break
        group_num += 1
    return now_ord, group_num, vis_i


@njit((i8, i8[:, :]), cache=True)
def scc(N, G):
    idx = np.searchsorted(G[:, 0], np.arange(N + 1))
    low = np.zeros(N, np.int64)
    ord = np.zeros(N, np.int64) - 1
    now_ord = 0
    group_num = 0
    visited, vis_i = np.empty(N, np.int64), 0
    ids = np.zeros(N, np.int64)
    for v in range(N):
        if ord[v] == -1:
            now_ord, group_num, vis_i = \
                scc_dfs(N, G, idx, low, ord, ids,
                        visited, now_ord, group_num,
                        vis_i, v)
    return group_num, group_num - ids - 1

@njit((i8, i8[:, :]), cache=True)
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 + 1))
    print(n_comp)
    for c in range(n_comp):
        V = ans[idx[c]:idx[c + 1], 0]
        print(len(V))
        for v in V:
            print(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)

Solution (Python):
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[:, :], i8[:], i8[:], i8[:], i8[:], i8[:], i8, i8, i8, i8),
      cache=True)
def scc_dfs(N, G, idx, low, ord, ids, visited, now_ord, group_num, vis_i, v):
    low[v] = ord[v] = now_ord
    now_ord += 1
    visited[vis_i], vis_i = v, vis_i + 1
    for e in range(idx[v], idx[v + 1]):
        to = G[e, 1]
        if ord[to] == -1:
            now_ord, group_num, vis_i = \
                scc_dfs(N, G, idx, low, ord, ids,
                        visited, now_ord, group_num,
                        vis_i, to)
            low[v] = min(low[v], low[to])
        else:
            low[v] = min(low[v], ord[to])
    if low[v] == ord[v]:
        while True:
            u, vis_i = visited[vis_i - 1], vis_i - 1
            ord[u] = N
            ids[u] = group_num
            if u == v:
                break
        group_num += 1
    return now_ord, group_num, vis_i


@njit((i8, i8[:, :]), cache=True)
def scc(N, G):
    idx = np.searchsorted(G[:, 0], np.arange(N + 1))
    low = np.zeros(N, np.int64)
    ord = np.zeros(N, np.int64) - 1
    now_ord = 0
    group_num = 0
    visited, vis_i = np.empty(N, np.int64), 0
    ids = np.zeros(N, np.int64)
    for v in range(N):
        if ord[v] == -1:
            now_ord, group_num, vis_i = \
                scc_dfs(N, G, idx, low, ord, ids,
                        visited, now_ord, group_num,
                        vis_i, v)
    return group_num, group_num - ids - 1

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 + 1))
    print(n_comp)
    for c in range(n_comp):
        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)

Solution (Python):
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 = [0]*N
    order = []
    for st in range(N):
        if used[st]:
            continue
        stack = [~st, st]
        while stack:
            vn = stack.pop()
            if vn >= 0:
                if used[vn]:
                    continue
                used[vn] = 1
                for vf in Edge[vn]:
                    if used[vf]:
                        continue
                    stack.append(~vf)
                    stack.append(vf)
            else:
                if used[~vn] != 2:
                    used[~vn] = 2
                    order.append(~vn)


    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


        
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 = scc(Edge)
Ans = [str(len(comp))]

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

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
n,m=map(int, input().split())
e=[[] for _ in range(n)]
e_rev=[[] for _ in range(n)]
for i in range(m):
    ai,bi=map(int, input().split())
    e[ai].append(bi)
    e_rev[bi].append(ai)

p_ord=[]
used=[0]*n
def dfs(v):
    used[v]=1
    for u in e[v]:
        if not used[u]:
            dfs(u)
    p_ord.append(v)
for i in range(n):
    if not used[i]:
        dfs(i)
compo = [0]*n
used=[0]*n
def dfs_rev(v,c):
    compo[v]=c
    used[v]=1
    for u in e_rev[v]:
        if not used[u]:
            dfs_rev(u,c)
cnt=0
for i in reversed(p_ord):
    if not used[i]:
        dfs_rev(i,cnt)
        cnt+=1
cc=[[] for _ in range(cnt+1)]
for i in range(n):
    cc[compo[i]].append(i)

print(len([cci for cci in cc if cci]))
for cci in cc:
    if cci:
        print(len(cci),*cci)

Solution (Python):
import sys
input = sys.stdin.readline

def dfs_numbering(st, M, V, ANS, cnt, v):
    ST = [st]
    while len(ST) > 0:
        i = ST[-1]
        if ANS[i] == -1:
            V[i] = v
            end = 1
            for x in M[i]:
                if V[x] == -1:
                    ST.append(x)
                    end = 0
            if end == 1:
                ST.pop()
                ANS[i] = cnt
                cnt += 1
        else:
            ST.pop()
    return cnt

class scc():
    def __init__(self, n):
        self.n = n
        self.M = [[] for i in range(n)]
        self.IM = [[] for i in range(n)]

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

    def scc_list(self):
        n = self.n
        V = [-1] * n
        ANS = [-1] * n

        cnt = 0
        for i in range(n):
            if V[i] == -1:
                cnt = dfs_numbering(i, self.M, V, ANS, cnt, 0)

        ANS1 = [[ANS[i], i] for i in range(n)]
        ANS1.sort(reverse=True)

        V = [-1] * n
        ANS = [-1] * n
        v = 0
        for i in range(n):
            if V[ANS1[i][1]] == -1:
                dfs_numbering(ANS1[i][1], self.IM, V, ANS, 0, v)
                v += 1

        FANS = [[] for i in range(v)]
        for i in range(n):
            FANS[V[i]].append(i)

        return FANS

n, m = map(int,input().split())

S = scc(n)
for i in range(m):
    frm, to = map(int,input().split())
    S.add_edge(frm, to)
ANS = S.scc_list()

print(len(ANS))
for i in range(len(ANS)):
    print(len(ANS[i]), end=" ")
    print(*ANS[i])

Solution (Python):
import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**6 + 5)

def dfs_numbering(st, M, V, ANS, cnt, v):
    ST = [st]
    while len(ST) > 0:
        
        i = ST[-1]
        if ANS[i] == -1:
            V[i] = v
            end = 1
            for x in M[i]:
                if V[x] == -1:
                    ST.append(x)
                    end = 0
                    
            if end == 1:
                ST.pop()
                ANS[i] = cnt
                cnt += 1
        else:
            ST.pop()
    return cnt

class scc():
    def __init__(self, n):
        self.n = n
        self.M = [[] for i in range(n)]
        self.IM = [[] for i in range(n)]

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

    def scc_list(self):
        n = self.n
        V = [-1] * n
        ANS = [-1] * n

        cnt = 0
        for i in range(n):
            if V[i] == -1:
                cnt = dfs_numbering(i, self.M, V, ANS, cnt, 0)

        

        ANS1 = [[ANS[i], i] for i in range(n)]
        ANS1.sort(reverse=True)

        

        V = [-1] * n
        ANS = [-1] * n
        v = 0
        for i in range(n):
            if V[ANS1[i][1]] == -1:
                dfs_numbering(ANS1[i][1], self.IM, V, ANS, 0, v)
                v += 1

        FANS = [[] for i in range(v)]
        for i in range(n):
            FANS[V[i]].append(i)

        return FANS

n, m = map(int,input().split())

S = scc(n)
for i in range(m):
    frm, to = map(int,input().split())
    S.add_edge(frm, to)
ANS = S.scc_list()

print(len(ANS))
for i in range(len(ANS)):
    print(len(ANS[i]), end=" ")
    print(*ANS[i])

Solution (Python):
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]

import sys
sys.setrecursionlimit(10**8)
class Scc:
    def __init__(self,n):
        self.n = n
        self.edges = []

    def add_edge(self,fr,to):
        assert 0 <= fr < self.n
        assert 0 <= to < self.n
        self.edges.append((fr, to))

    def scc(self):
        csr_start = [0] * (self.n + 1)
        csr_elist = [0] * len(self.edges)
        for fr,to in self.edges:
            csr_start[fr + 1] += 1
        for i in range(1,self.n+1):
            csr_start[i] += csr_start[i-1]
        counter = csr_start[:]
        for fr,to in self.edges:
            csr_elist[counter[fr]] = to
            counter[fr] += 1

        self.now_ord = self.group_num = 0
        self.visited = []
        self.low = [0] * self.n
        self.ord = [-1] * self.n
        self.ids = [0] * self.n
        def _dfs(v):
            self.low[v] = self.ord[v] = self.now_ord
            self.now_ord += 1
            self.visited.append(v)
            for i in range(csr_start[v], csr_start[v+1]):
                to = csr_elist[i]
                if self.ord[to] == -1:
                    _dfs(to)
                    self.low[v] = min(self.low[v], self.low[to])
                else:
                    self.low[v] = min(self.low[v], self.ord[to])
            if self.low[v] == self.ord[v]:
                while 1:
                    u = self.visited.pop()
                    self.ord[u] = self.n
                    self.ids[u] = self.group_num
                    if u==v: break
                self.group_num += 1
        for i in range(self.n):
            if self.ord[i] == -1: _dfs(i)
        for i in range(self.n):
            self.ids[i] = self.group_num - 1 - self.ids[i]

        groups = [[] for _ in range(self.group_num)]
        for i in range(self.n):
            groups[self.ids[i]].append(i)
        return groups

scc = Scc(N)
for a,b in AB:
    scc.add_edge(a,b)
ans = scc.scc()
print(len(ans))
for row in ans:
    print(*[len(row)] + row)

Solution (Python):

from collections import defaultdict

def scc(V, E):
    g = defaultdict(list)
    rg = defaultdict(list)
    for u, v in E:
        g[u].append(v)
        rg[v].append(u)


    o = []
    done = set()
    for u in V:
        if u in done:
            continue

        s = [(u, True)]
        while s:
            u, f = s.pop()
            if f:
                if u in done:
                    continue
                done.add(u)
                s.append((u, False))
                for v in g[u]:
                    if v in done:
                        continue
                    s.append((v, True))
            else:
                o.append(u)

    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue

        s = [u]
        vv = [u]
        done.add(u)
        while s:
            u = s.pop()
            for v in rg[u]:
                if v in done:
                    continue
                vv.append(v)
                s.append(v)
                done.add(v)
        ans.append(vv)


    return ans


def atcoder_practice2_g():
    
    import sys
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())

    E = []
    for _ in range(M):
        a, b = map(int, input().split())
        E.append((a, b))
    V = list(range(N))
    vv = scc(V, E)
    print(len(vv))
    for r in vv:
        print(len(r), *r)


if __name__ == "__main__":
    atcoder_practice2_g()

Solution (Python):

from collections import defaultdict
import sys

input = sys.stdin.buffer.readline

def scc(V, E):
    g = defaultdict(list)
    
    rg = defaultdict(list)
    
    for u, v in E:
        g[u].append(v)
        rg[v].append(u)


    o = []
    done = set()
    for u in V:
        if u in done:
            continue

        s = [(u, True)]
        while s:
            u, f = s.pop()
            if f:
                if u in done:
                    continue
                done.add(u)
                s.append((u, False))
                for v in g[u]:
                    if v in done:
                        continue
                    s.append((v, True))
            else:
                o.append(u)

    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue

        s = [u]
        vv = [u]
        done.add(u)
        while s:
            u = s.pop()
            for v in rg[u]:
                if v in done:
                    continue
                vv.append(v)
                s.append(v)
                done.add(v)
        ans.append(vv)


    return ans


def atcoder_practice2_g():
    N, M = map(int, input().split())

    E = []
    for _ in range(M):
        a, b = map(int, input().split())
        E.append((a, b))
    V = list(range(N))
    vv = scc(V, E)
    print(len(vv))
    for r in vv:
        print(len(r), *r)


def test():
    g = {
        1: [2],
        5: [2],
        2: [4, 3],
        3: [4, 7, 6],
        4: [5, 8],
        6: [9],
        7: [8],
        8: [9],
        9: [7, 10],
        10: []
    }

    V = list(range(1, 11))
    E = []
    for u, e in g.items():
        for v in e:
            E.append((u, v))

    vv = scc(V, E)
    for r in vv:
        print(r)


if __name__ == "__main__":
    
    atcoder_practice2_g()

Solution (Python):

from collections import defaultdict
import sys

input = sys.stdin.buffer.readline

def scc(V, E):
    
    g = [[] for _ in range(len(V))]
    
    rg = [[] for _ in range(len(V))]
    for u, v in E:
        g[u].append(v)
        rg[v].append(u)


    o = []
    done = set()
    for u in V:
        if u in done:
            continue

        s = [(u, True)]
        while s:
            u, f = s.pop()
            if f:
                if u in done:
                    continue
                done.add(u)
                s.append((u, False))
                for v in g[u]:
                    if v in done:
                        continue
                    s.append((v, True))
            else:
                o.append(u)

    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue

        s = [u]
        vv = [u]
        done.add(u)
        while s:
            u = s.pop()
            for v in rg[u]:
                if v in done:
                    continue
                vv.append(v)
                s.append(v)
                done.add(v)
        ans.append(vv)


    return ans


def atcoder_practice2_g():
    N, M = map(int, input().split())

    E = []
    for _ in range(M):
        a, b = map(int, input().split())
        E.append((a, b))
    V = list(range(N))
    vv = scc(V, E)
    print(len(vv))
    for r in vv:
        print(len(r), *r)


def test():
    g = {
        1: [2],
        5: [2],
        2: [4, 3],
        3: [4, 7, 6],
        4: [5, 8],
        6: [9],
        7: [8],
        8: [9],
        9: [7, 10],
        10: []
    }

    V = list(range(1, 11))
    E = []
    for u, e in g.items():
        for v in e:
            E.append((u, v))

    vv = scc(V, E)
    for r in vv:
        print(r)


if __name__ == "__main__":
    
    atcoder_practice2_g()

Solution (Python):

from collections import defaultdict
import sys

input = sys.stdin.buffer.readline

def scc(V, E):
    
    g = [list() for _ in range(len(V))]
    
    rg = [list() for _ in range(len(V))]
    for u, v in E:
        g[u].append(v)
        rg[v].append(u)


    o = []
    done = set()
    for u in V:
        if u in done:
            continue

        s = [(u, True)]
        while s:
            u, f = s.pop()
            if f:
                if u in done:
                    continue
                done.add(u)
                s.append((u, False))
                for v in g[u]:
                    if v in done:
                        continue
                    s.append((v, True))
            else:
                o.append(u)

    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue

        s = [u]
        vv = [u]
        done.add(u)
        while s:
            u = s.pop()
            for v in rg[u]:
                if v in done:
                    continue
                vv.append(v)
                s.append(v)
                done.add(v)
        ans.append(vv)


    return ans


def atcoder_practice2_g():
    N, M = map(int, input().split())

    E = []
    for _ in range(M):
        a, b = map(int, input().split())
        E.append((a, b))
    V = list(range(N))
    vv = scc(V, E)
    print(len(vv))
    for r in vv:
        print(len(r), *r)


def test():
    g = {
        1: [2],
        5: [2],
        2: [4, 3],
        3: [4, 7, 6],
        4: [5, 8],
        6: [9],
        7: [8],
        8: [9],
        9: [7, 10],
        10: []
    }

    V = list(range(1, 11))
    E = []
    for u, e in g.items():
        for v in e:
            E.append((u, v))

    vv = scc(V, E)
    for r in vv:
        print(r)


if __name__ == "__main__":
    
    atcoder_practice2_g()

Solution (Python):

from collections import defaultdict
import sys

input = sys.stdin.buffer.readline

def scc(V, E):
    g = defaultdict(list)
    rg = defaultdict(list)
    for u, v in E:
        g[u].append(v)
        rg[v].append(u)


    o = []
    done = set()
    for u in V:
        if u in done:
            continue

        s = [(u, True)]
        while s:
            u, f = s.pop()
            if f:
                if u in done:
                    continue
                done.add(u)
                s.append((u, False))
                for v in g[u]:
                    if v in done:
                        continue
                    s.append((v, True))
            else:
                o.append(u)

    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue

        s = [u]
        vv = [u]
        done.add(u)
        while s:
            u = s.pop()
            for v in rg[u]:
                if v in done:
                    continue
                vv.append(v)
                s.append(v)
                done.add(v)
        ans.append(vv)


    return ans


def atcoder_practice2_g():
    N, M = map(int, input().split())

    E = []
    for _ in range(M):
        a, b = map(int, input().split())
        E.append((a, b))
    V = list(range(N))
    vv = scc(V, E)
    print(len(vv))
    for r in vv:
        print(len(r), *r)


def test():
    g = {
        1: [2],
        5: [2],
        2: [4, 3],
        3: [4, 7, 6],
        4: [5, 8],
        6: [9],
        7: [8],
        8: [9],
        9: [7, 10],
        10: []
    }

    V = list(range(1, 11))
    E = []
    for u, e in g.items():
        for v in e:
            E.append((u, v))

    vv = scc(V, E)
    for r in vv:
        print(r)


if __name__ == "__main__":
    
    atcoder_practice2_g()