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):
mod = 1000000007
eps = 10**-9


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

    from collections import deque

    
    
    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

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

Solution (Python):
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)]


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)

Solution (Python):
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]


def scc(G):
    preorder = {}
    lowlink = {}
    seen = [False] * N
    scc_queue = []
    i = 0  
    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)

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 = [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))

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 = [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))

Solution (Python):
from collections import deque

class Graph():  
    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() 
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)))

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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])

Solution (Python):
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])

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[:, :]), 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)

Solution (Python):

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

Solution (Python):
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

        
        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)

        
        self.post_order = []
        self.used = [False] * self.n
        for v in range(self.n):
            if not self.used[v]:
                self._dfs(v)

        
        
        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

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

Solution (Python):
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  
    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)))