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






class csr:
    def __init__(self, n, edges):
        from copy import deepcopy
        self.start = [0] * (n + 1)
        self.elist = [[] for _ in range(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 = deepcopy(self.start)
        for e in edges:
            self.elist[counter[e[0]]] = e[1]; counter[e[0]] += 1

class scc_graph:
    '''
    Reference:
    R. Tarjan,
    Depth-First Search and Linear Graph Algorithms
    '''
    
    edges = []
    
    
    def __init__(self, n: int): self._n = n
    
    def num_vertices(self): return self._n

    def add_edge(self, _from: int, _to: int): self.edges.append((_from, [_to]))
    
    def scc_ids(self):
        g = csr(self._n, self.edges)
        self.now_ord = 0; self.group_num = 0
        visited = []; low = [0] * self._n; ord = [-1] * self._n; ids = [0] * self._n
        
        def dfs(s, v):
            low[v] = ord[v] = self.now_ord; self.now_ord += 1
            visited.append(v)
            for i in range(g.start[v], g.start[v + 1]):
                to = g.elist[i][0]
                if ord[to] == -1:
                    s(s, to)
                    low[v] = min(low[v], low[to])
                else:
                    low[v] = min(low[v], ord[to])
            if low[v] == ord[v]:
                while True:
                    u = visited.pop()
                    ord[u] = self._n
                    ids[u] = self.group_num
                    if u == v: break
                self.group_num += 1

        for i in range(self._n):
            if ord[i] == -1: dfs(dfs, i)
        for i in range(self._n):
            ids[i] = self.group_num - 1 - ids[i]
        return (self.group_num, ids)
        
    def scc(self):
        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

import sys








sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, m = read_ints()
    
    scc = scc_graph(n)
    for _ in range(m):
        a, b = read_ints()
        scc.add_edge(a, b)
    ans = scc.scc()

    print(len(ans))
    for v in ans:
        print(len(v), ' '.join(map(str, v[::-1])))

if __name__ == '__main__':
    Main()

Solution (Python):




import copy
import sys
sys.setrecursionlimit(1000000)

class csr:
  
  
  def __init__(s, n, edges):
    s.start = [0] * (n + 1)
    s.elist = [[] for _ in range(len(edges))]
    for e in edges:
      s.start[e[0] + 1] += 1
    for i in range(1, n + 1):
      s.start[i] += s.start[i - 1]
    counter = copy.deepcopy(s.start)
    for e in edges:
      s.elist[counter[e[0]]] = e[1]
      counter[e[0]] += 1

class scc_graph:

  edges = []

  
  def __init__(s, n): s._n = n
  def num_vertices(s): return s._n
  
  
  def add_edge(s, frm, to): s.edges.append([frm, [to]])

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

    for i in range(s._n):
      if ord[i] == -1: now_ord, group_num = dfs(dfs, i, now_ord, group_num)
    for i in range(s._n):
      ids[i] = group_num - 1 - ids[i]
    return [group_num, ids]

  
  
  def scc(s):
    ids = s.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(s._n):
      groups[ids[1][i]].append(i)
    return groups




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

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

  g = scc_graph(n)

  for i in range(m):
    u, v = ab[i]
    g.add_edge(u, v)

  scc = g.scc()

  print(len(scc))

  for v in scc:
    print(len(v), end = " ")
    for x in v:
      print(x, end = " ")
    print("")

main()

Solution (Python):




import copy
import sys
sys.setrecursionlimit(1000000)

class csr:
  
  
  def __init__(s, n, edges):
    s.start = [0] * (n + 1)
    s.elist = [[] for _ in range(len(edges))]
    for e in edges:
      s.start[e[0] + 1] += 1
    for i in range(1, n + 1):
      s.start[i] += s.start[i - 1]
    counter = copy.deepcopy(s.start)
    for e in edges:
      s.elist[counter[e[0]]] = e[1]
      counter[e[0]] += 1

class scc_graph:

  edges = []

  
  def __init__(s, n): s._n = n
  def num_vertices(s): return s._n
  
  
  def add_edge(s, frm, to): s.edges.append([frm, [to]])

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

    for i in range(s._n):
      if ord[i] == -1: now_ord, group_num = dfs(dfs, i, now_ord, group_num)
    for i in range(s._n):
      ids[i] = group_num - 1 - ids[i]
    return [group_num, ids]

  
  
  def scc(s):
    ids = s.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(s._n):
      groups[ids[1][i]].append(i)
    return groups




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

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

  g = scc_graph(n)

  for i in range(m):
    u, v = ab[i]
    g.add_edge(u, v)

  scc = g.scc()

  print(len(scc))

  for v in scc:
    print(len(v), end = " ")
    for x in v:
      print(x, end = " ")
    print("")

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def MI(): return map(int,sys.stdin.readline().rstrip().split())


class SCC:
    def __init__(self,N):
        self.N = N
        self.graph = [[] for _ in range(N)]
        self.graph_rev = [[] for _ in range(N)]
        self.flag = [False]*N

    def add_edge(self,start,end):
        if start == end:
            return
        self.graph[start].append(end)
        self.graph_rev[end].append(start)

    def dfs(self,node,graph):
        self.flag[node] = True
        for n in graph[node]:
            if self.flag[n]:
                continue
            self.dfs(n,graph)
        self.order.append(node)

    def first_dfs(self):
        self.flag = [False]*self.N
        self.order = []
        for i in range(self.N):
            if self.flag[i] == False:
                self.dfs(i,self.graph)

    def second_dfs(self):
        self.flag = [False]*self.N
        self.ans = []
        for n in reversed(self.order):
            if self.flag[n]:
                continue
            self.flag[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


N,M = MI()
SCC = SCC(N)

for _ in range(M):
    a,b = MI()
    SCC.add_edge(a,b)

ANS = SCC.scc()

print(len(ANS))
for s in ANS:
    print(*([len(s)]+s))

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    def scc(n, links, rev_links):
        stack = np.zeros(n * 2, np.int64)
        checked = np.zeros(n, np.int8)
        postorder = np.zeros(n, np.int64)
        pi = 0

        for v in range(n):
            if checked[v]:
                continue

            
            stack[0] = 0
            stack[1] = v
            si = 2
            while si > 0:
                i = stack[si - 2]
                v = stack[si - 1]
                if i == 0 and checked[v]:
                    si -= 2
                    continue
                checked[v] = 1
                l = len(links[v])
                while i < l and checked[links[v][i]] == 1:
                    i += 1
                if i == l:
                    postorder[pi] = v
                    pi += 1
                    si -= 2
                    continue
                stack[si - 2] = i + 1
                stack[si] = 0
                stack[si + 1] = links[v][i]
                si += 2

        postorder = postorder[::-1]
        checked = np.zeros(n, np.int8)
        sccs = []

        for v in postorder:
            if checked[v]:
                continue

            
            stack[0] = v
            si = 1
            checked[v] = 1
            scc = [v]
            while si > 0:
                si -= 1
                v = stack[si]
                for u in rev_links[v]:
                    if checked[u] == 0:
                        checked[u] = 1
                        stack[si] = u
                        si += 1
                        scc.append(u)
            sccs.append(scc)

        return sccs

    n = inp[0]
    m = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    int_list = [0]
    int_list.clear()
    links = [int_list.copy() for _ in range(n)]
    rev_links = [int_list.copy() for _ in range(n)]

    for i in range(m):
        a = aaa[i]
        b = bbb[i]
        if a != b:
            links[a].append(b)
            rev_links[b].append(a)

    return scc(n, links, rev_links)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(len(ans))
for scc in ans:
    print(len(scc), *scc)

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    def scc_dfs1(links, s, stack, checked, postorder, pi):
        stack[0] = 0
        stack[1] = s
        si = 2
        while si > 0:
            i = stack[si - 2]
            v = stack[si - 1]
            if i == 0 and checked[v]:
                si -= 2
                continue
            checked[v] = 1
            l = len(links[v])
            while i < l and checked[links[v][i]] == 1:
                i += 1
            if i == l:
                postorder[pi] = v
                pi += 1
                si -= 2
                continue
            stack[si - 2] = i + 1
            stack[si] = 0
            stack[si + 1] = links[v][i]
            si += 2
        return pi

    def scc_dfs2(rev_links, s, stack, checked):
        stack[0] = s
        si = 1
        checked[s] = 1
        scc = [s]
        while si > 0:
            si -= 1
            v = stack[si]
            for u in rev_links[v]:
                if checked[u] == 0:
                    checked[u] = 1
                    stack[si] = u
                    si += 1
                    scc.append(u)
        return scc

    def scc(n, links, rev_links):
        stack = np.zeros(n * 2, np.int64)
        checked = np.zeros(n, np.int8)
        postorder = np.zeros(n, np.int64)
        pi = 0

        for v in range(n):
            if checked[v]:
                continue
            pi = scc_dfs1(links, v, stack, checked, postorder, pi)

        postorder = postorder[::-1]
        checked = np.zeros(n, np.int8)
        sccs = []

        for v in postorder:
            if checked[v]:
                continue
            sccs.append(scc_dfs2(rev_links, v, stack, checked))

        return sccs

    n = inp[0]
    m = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    int_list = [0]
    int_list.clear()
    links = [int_list.copy() for _ in range(n)]
    rev_links = [int_list.copy() for _ in range(n)]

    for i in range(m):
        a = aaa[i]
        b = bbb[i]
        if a != b:
            links[a].append(b)
            rev_links[b].append(a)

    return scc(n, links, rev_links)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(len(ans))
for scc in ans:
    print(len(scc), *scc)

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    def scc_dfs1(links, s, stack, checked, postorder, pi):
        stack[0] = 0
        stack[1] = s
        si = 2
        while si > 0:
            i = stack[si - 2]
            v = stack[si - 1]
            if i == 0 and checked[v]:
                si -= 2
                continue
            checked[v] = 1
            l = len(links[v])
            while i < l and checked[links[v][i]] == 1:
                i += 1
            if i == l:
                postorder[pi] = v
                pi += 1
                si -= 2
                continue
            stack[si - 2] = i + 1
            stack[si] = 0
            stack[si + 1] = links[v][i]
            si += 2
        return pi

    def scc_dfs2(rev_links, s, stack, checked):
        stack[0] = s
        si = 1
        checked[s] = 1
        scc = [s]
        while si > 0:
            si -= 1
            v = stack[si]
            for u in rev_links[v]:
                if checked[u] == 0:
                    checked[u] = 1
                    stack[si] = u
                    si += 1
                    scc.append(u)
        return scc

    def scc(n, links, rev_links):
        stack = np.zeros(n * 5, np.int64)
        checked = np.zeros(n, np.int8)
        postorder = np.zeros(n, np.int64)
        pi = 0

        for v in range(n):
            if checked[v]:
                continue
            pi = scc_dfs1(links, v, stack, checked, postorder, pi)

        postorder = postorder[::-1]
        checked = np.zeros(n, np.int8)
        sccs = []

        for v in postorder:
            if checked[v]:
                continue
            sccs.append(scc_dfs2(rev_links, v, stack, checked))

        return sccs

    n = inp[0]
    m = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    int_list = [0]
    int_list.clear()
    links = [int_list.copy() for _ in range(n)]
    rev_links = [int_list.copy() for _ in range(n)]

    for i in range(m):
        a = aaa[i]
        b = bbb[i]
        if a != b:
            links[a].append(b)
            rev_links[b].append(a)

    return scc(n, links, rev_links)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(len(ans))
for scc in ans:
    print(len(scc), *scc)

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    def dfs(links, s, checked, postorder):
        stack = [0, s]
        while stack:
            i, v = stack[-2:]
            if i == 0 and checked[v]:
                stack.pop()
                stack.pop()
                continue
            checked[v] = 1
            l = len(links[v])
            while i < l and checked[links[v][i]] == 1:
                i += 1
            if i == l:
                postorder.append(v)
                stack.pop()
                stack.pop()
                continue
            stack[-2] = i + 1
            stack.append(0)
            stack.append(links[v][i])

    def dfs2(rev_links, s, checked):
        q = [s]
        checked[s] = 1
        scc = [s]
        while q:
            v = q.pop()
            for u in rev_links[v]:
                if checked[u] == 0:
                    q.append(u)
                    checked[u] = 1
                    scc.append(u)
        return scc

    n = inp[0]
    m = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    int_list = [0]
    int_list.clear()
    links = [int_list.copy() for _ in range(n)]
    rev_links = [int_list.copy() for _ in range(n)]

    for i in range(m):
        a = aaa[i]
        b = bbb[i]
        if a != b:
            links[a].append(b)
            rev_links[b].append(a)

    checked = np.zeros(n, np.int8)
    postorder = []

    for v in range(n):
        if checked[v]:
            continue
        dfs(links, v, checked, postorder)

    postorder.reverse()
    checked = np.zeros(n, np.int8)
    sccs = []

    for v in postorder:
        if checked[v]:
            continue
        sccs.append(dfs2(rev_links, v, checked))

    return sccs


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(len(ans))
for scc in ans:
    print(len(scc), *scc)

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    def dfs(links, s, checked, postorder):
        stack = [0, s]
        while stack:
            i, v = stack[-2:]
            if i == 0 and checked[v]:
                stack.pop()
                stack.pop()
                continue
            checked[v] = 1
            if i == len(links[v]):
                postorder.append(v)
                stack.pop()
                stack.pop()
                continue
            stack[-2] += 1
            stack.append(0)
            stack.append(links[v][i])

    def dfs2(rev_links, s, checked):
        q = [s]
        checked[s] = 1
        scc = [s]
        while q:
            v = q.pop()
            for u in rev_links[v]:
                if checked[u] == 0:
                    q.append(u)
                    checked[u] = 1
                    scc.append(u)
        return scc

    n = inp[0]
    m = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    int_list = [0]
    int_list.clear()
    links = [int_list.copy() for _ in range(n)]
    rev_links = [int_list.copy() for _ in range(n)]

    for i in range(m):
        a = aaa[i]
        b = bbb[i]
        if a != b:
            links[a].append(b)
            rev_links[b].append(a)

    checked = np.zeros(n, np.int8)
    postorder = []

    for v in range(n):
        if checked[v]:
            continue
        dfs(links, v, checked, postorder)

    postorder.reverse()
    checked = np.zeros(n, np.int8)
    sccs = []

    for v in postorder:
        if checked[v]:
            continue
        sccs.append(dfs2(rev_links, v, checked))

    return sccs


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(len(ans))
for scc in ans:
    print(len(scc), *scc)

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    def dfs(links, s, checked, postorder):
        stack = [0, s]
        while stack:
            i, v = stack[-2:]
            if i == 0 and checked[v]:
                stack.pop()
                stack.pop()
                continue
            checked[v] = 1
            if i == len(links[v]):
                postorder.append(v)
                stack.pop()
                stack.pop()
                continue
            stack[-2] += 1
            stack.append(0)
            stack.append(links[v][i])

    def dfs2(rev_links, s, checked):
        q = [s]
        checked[s] = 1
        scc = [s]
        while q:
            v = q.pop()
            for u in rev_links[v]:
                if checked[u] == 0:
                    q.append(u)
                    checked[u] = 1
                    scc.append(u)
        return scc

    n = inp[0]
    m = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    int_list = [0]
    int_list.clear()
    links = [int_list.copy() for _ in range(n)]
    rev_links = [int_list.copy() for _ in range(n)]

    for i in range(m):
        a = aaa[i]
        b = bbb[i]
        if a != b:
            links[a].append(b)
            rev_links[b].append(a)
    links = [list(set(link)) for link in links]
    rev_links = [list(set(link)) for link in rev_links]

    checked = np.zeros(n, np.int8)
    postorder = []

    for v in range(n):
        if checked[v]:
            continue
        dfs(links, v, checked, postorder)

    postorder.reverse()
    checked = np.zeros(n, np.int8)
    sccs = []

    for v in postorder:
        if checked[v]:
            continue
        sccs.append(dfs2(rev_links, v, checked))

    return sccs


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(len(ans))
for scc in ans:
    print(len(scc), *scc)

Solution (Python):
class Digraph:
    """重み[なし]有向グラフを生成する.

    """

    
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:set() for v in vertex} 
        self.adjacent_in={v:set() for v in vertex} 

    
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]=set()
                self.adjacent_out[v]=set()

                self.vertex_number+=1
                self.vertex.add(v)

    
    def add_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From].add(To)
        self.adjacent_in[To].add(From)

    
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To in self.adjacent_out[From]:
            self.adjacent_out[From].remove(To)
            self.adjacent_in[To].remove(From)
            self.edge_number-=1

    
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    self.adjacent_in[u].remove(v)
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    self.adjacent_out[u].remove(v)
                    self.edge_number-=1
                del self.adjacent_in[v]

    
    def add_walk(self,*walk):
        N=len(walk)
        for k in range(N-1):
            self.add_edge(walk[k],walk[k+1])

    
    def add_cycle(self,*cycle):
        self.add_walk(*cycle)
        self.add_edge(cycle[-1],cycle[0])

    
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    
    def vertex_exist(self,v):
        return v in self.vertex

    
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    
    def vertex_count(self):
        return len(self.vertex)

    
    def edge_count(self):
        return self.edge_number

    
    def connected_component(self,v):
        pass


def Topological_Sort(D):
    from collections import deque

    X={v:D.in_degree(v) for v in D.vertex}
    Q=deque([v for v in D.vertex if X[v]==0])

    S=[]
    while Q:
        u=Q.pop()
        S.append(u)
        for v in D.adjacent_out[u]:
            X[v]-=1
            if X[v]==0:
                Q.append(v)

    return S


def Strongly_Connected_Component_Decomposition(D,Mode=0):
    """有向グラフDを強連結成分に分解

    Mode:
    0(Defalt)---各強連結成分の頂点のリスト
    1        ---各頂点が属している強連結成分の番号
    2        ---0,1の両方

    ※0で帰ってくるリストは各強連結成分に関してトポロジカルソートである.
    """
    import sys
    from collections import deque

    T={x:-1 for x in D.vertex}
    Q=deque([])

    def f(v):
        T[v]=0
        for w in D.adjacent_out[v]:
            if T[w]==-1:
                f(w)

        Q.appendleft(v)
        T[v]=len(Q)
    x=D.vertex.pop()
    D.vertex.add(x)

    RT=sys.getrecursionlimit()
    sys.setrecursionlimit(3*10**5)
    for v in D.vertex:
        if T[v]==-1:
            f(v)
    sys.setrecursionlimit(RT)

    T={x:-1 for x in D.vertex}
    C=[]
    p=0

    for v in Q:
        if T[v]==-1:
            T[v]=p
            P=[v]
            R=deque([v])

            while R:
                u=R.popleft()
                for w in D.adjacent_in[u]:
                    if T[w]==-1:
                        T[w]=p
                        R.append(w)
                        P.append(w)
            C.append(P)
            p+=1

    if Mode==1:
        return T
    elif Mode==2:
        return (C,T)
    else:
        return C

N,M=map(int,input().split())
D=Digraph(list(range(N)))

for _ in range(M):
    a,b=map(int,input().split())
    D.add_edge(a,b)

C=Strongly_Connected_Component_Decomposition(D)

X=[""]*(len(C))
for i in range(len(C)):
    X[i]="{} {}".format(len(C[i])," ".join(map(str,C[i])))

print(len(C))
print("\n".join(X))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools


sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)
def IF(c, t, f): return t if c else f

def scc(n, e, re):
    v = [None] * n
    t = []
    def dfs(i):
        v[i] = 0
        for b in e[i]:
            if v[b] is None:
                dfs(b)
        t.append(i)

    for i in range(n):
        if v[i] is None:
            dfs(i)

    r = [None] * n
    def dfs2(i, p):
        r[i] = p
        for b in re[i]:
            if r[b] is None:
                dfs2(b, p)

    for c in t[::-1]:
        if r[c] is None:
            dfs2(c, c)

    return r


def main():
    n,m = LI()
    ab = [LI() for _ in range(m)]

    e = collections.defaultdict(set)
    re = collections.defaultdict(set)
    for a,b in ab:
        e[a].add(b)
        re[b].add(a)

    sc = scc(n,e,re)
    d = {}
    ci = collections.defaultdict(list)
    for i,c in enumerate(sc):
        ci[c].append(i)
        d[i] = c

    cs = list(ci.keys())
    se = collections.defaultdict(set)
    sre = collections.defaultdict(set)
    for a,b in ab:
        if d[a] == d[b]:
            continue
        se[d[a]].add(d[b])
        sre[d[b]].add(d[a])

    rr = []
    q = []
    for c in cs:
        if len(sre[c]) == 0:
            q.append(c)

    qi = 0
    while qi < len(q):
        c = q[qi]
        qi += 1
        rr.append(JA([len(ci[c])] + ci[c], " "))
        for nc in se[c]:
            sre[nc].remove(c)
            if len(sre[nc]) == 0:
                q.append(nc)

    return JA([len(rr)] + rr, "\n")


print(main())