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 StronglyConnectedComponents():
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.rev = [[] for _ in range(n)]

    def add_edge(self, fr, to):
        self.graph[fr].append(to)
        self.rev[to].append(fr)

    def scc_id(self):
        group = [-1] * self.n
        vis = [0] * self.n
        order = []
        for s in range(self.n):
            if vis[s]: continue
            stack = [s]
            vis[s] = True
            while stack:
                node = stack.pop()
                for adj in self.graph[node]:
                    if vis[adj]: continue
                    vis[adj] = True
                    stack.append(node)
                    stack.append(adj)
                    break
                else:
                    order.append(node)
        cnt = 0
        for s in order[::-1]:
            if group[s] != -1: continue
            stack = [s]
            group[s] = cnt
            while stack:
                node = stack.pop()
                for adj in self.rev[node]:
                    if group[adj] != -1: continue
                    group[adj] = cnt
                    stack.append(adj)
            cnt += 1
        return group, cnt

    def scc(self):
        group, cnt = self.scc_id()
        res = [[] for _ in range(cnt)]
        for i in range(self.n):
            res[group[i]].append(i)
        return res

import sys
input = sys.stdin.buffer.readline

N, M = map(int, input().split())

scc = StronglyConnectedComponents(N)

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

res = scc.scc()
print(len(res))

for r in res:
    print(len(r), *r)

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.frm + 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.frm]] = e.to
      counter[e.frm] += 1

class scc_graph:
  
  def __init__(s, n): 
    s._n = n
    s.edges = []
  def num_vertices(s): return s._n
  
  
  def add_edge(s, frm, to): s.edges.append(s.edge(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]
        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

  class edge:
    def __init__(s, frm, to):
      s.frm = frm
      s.to = to




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

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class DAG:
    def __init__(self, n, AB):
        self.n = n
        self.G = [[] for _ in range(n)]
        self.revG = [[] for _ in range(n)]
        self.AB = AB
        for a, b in AB:
            self.G[a].append(b)
            self.revG[b].append(a)

    def scc(self):
        visited = [False] * self.n
        order = []
        for i in range(self.n):
            if visited[i]: continue

            q = deque([i])
            visited[i] = True
            while q:
                v = q[-1]
                for u in self.G[v]:
                    if not visited[u]:
                        q.append(u)
                        visited[u] = True
                        break
                else:
                    
                    q.pop()
                    order.append(v)

        visited = [False] * self.n
        scc = []
        for i in order[::-1]:
            if visited[i]: continue
            tmp = [i]
            visited[i] = True
            q = deque([i])

            while q:
                v = q.pop()
                for u in self.revG[v]:
                    if visited[u]: continue
                    visited[u] = True
                    tmp.append(u)
                    q.append(u)
            scc.append(tmp)

        return scc



def main():
    N, M = LI()
    AB = LIR(M)
    g = DAG(N, AB)
    scc = g.scc()
    print(len(scc))
    for es in scc:
        print(len(es), *es)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def input():
	return sys.stdin.buffer.readline()[:-1]

class SCC():
	def __init__(self, adj):
		self.n = len(adj)
		self.adj = adj
		self.post_order = []
		self.visited = [False for _ in range(self.n)]
		self.dag_v_to_num = [-1 for _ in range(self.n)]
		self.dag_num_to_v = []
		self.inv = [[] for _ in range(self.n)]
		for i, l in enumerate(self.adj):
			for j in l:
				self.inv[j].append(i)
		return

	def dfs1(self, i):
		for j in adj[i]:
			if not self.visited[j]:
				self.visited[j] = True
				self.dfs1(j)
		self.post_order.append(i)
		return

	def dfs2(self, i, num):
		self.dag_num_to_v[-1].append(i)
		self.dag_v_to_num[i] = num
		for j in self.inv[i]:
			if not self.visited[j]:
				self.visited[j] = True
				self.dfs2(j, num)
		return

	def make_scc(self):
		for i in range(self.n):
			if not self.visited[i]:
				self.visited[i] = True
				self.dfs1(i)

		self.visited = [False for _ in range(self.n)]
		num = 0
		for i in range(self.n-1, -1, -1):
			if not self.visited[self.post_order[i]]:
				self.visited[self.post_order[i]] = True
				self.dag_num_to_v.append(list())
				self.dfs2(self.post_order[i], num)
				num += 1

		return self.dag_v_to_num, self.dag_num_to_v

n, m = map(int, input().split())
adj = [set() for _ in range(n)]
for _ in range(m):
	u, v = map(int, input().split())
	if u != v:
		adj[u].add(v)
adj = [list(x) for x in adj]
scc = SCC(adj)
v_to_num, num_to_v = scc.make_scc()
print(len(num_to_v))
for x in num_to_v:
	print(len(x), end=" ")
	print(*x)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def input():
	return sys.stdin.buffer.readline()[:-1]

class SCC():
	def __init__(self, adj):
		self.n = len(adj)
		self.adj = adj
		self.post_order = []
		self.visited = [False for _ in range(self.n)]
		self.dag_v_to_num = [-1 for _ in range(self.n)]
		self.dag_num_to_v = []
		self.inv = [[] for _ in range(self.n)]
		for i, l in enumerate(self.adj):
			for j in l:
				self.inv[j].append(i)
		return

	def dfs1(self, i):
		for j in adj[i]:
			if not self.visited[j]:
				self.visited[j] = True
				self.dfs1(j)
		self.post_order.append(i)
		return

	def dfs2(self, i, num):
		self.dag_num_to_v[-1].append(i)
		self.dag_v_to_num[i] = num
		for j in self.inv[i]:
			if not self.visited[j]:
				self.visited[j] = True
				self.dfs2(j, num)
		return

	def make_scc(self):
		for i in range(self.n):
			if not self.visited[i]:
				self.visited[i] = True
				self.dfs1(i)

		self.visited = [False for _ in range(self.n)]
		num = 0
		for i in range(self.n-1, -1, -1):
			if not self.visited[self.post_order[i]]:
				self.visited[self.post_order[i]] = True
				self.dag_num_to_v.append(list())
				self.dfs2(self.post_order[i], num)
				num += 1

		return self.dag_v_to_num, self.dag_num_to_v

n, m = map(int, input().split())
adj = [set() for _ in range(n)]
for _ in range(m):
	u, v = map(int, input().split())
	if u != v:
		adj[u].add(v)
adj = [list(x) for x in adj]
scc = SCC(adj)
v_to_num, num_to_v = scc.make_scc()
print(len(num_to_v))
for x in num_to_v:
	print(len(x), end=" ")
	print(*x)

Solution (Python):
class Graph(): 
    def __init__(self, n, edge, indexed=1):
        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] - indexed].append(e[1] - indexed)
            self.rev[e[1] - indexed].append(e[0] - indexed)
            self.deg[e[1] - indexed] += 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

import sys
input = sys.stdin.buffer.readline

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

g = Graph(N, E, 0)
group, count = g.strongry_connected()

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

for i, k in enumerate(group):
    res[k].append(i)

print(count)

for r in res:
    print(len(r), *r)

Solution (Python):
code = r"""


from libcpp.vector cimport vector
cdef extern from "<atcoder/scc>" namespace "atcoder" nogil:
    cdef cppclass scc_graph:
        scc_graph(int n)
        void add_edge(int fr, int to)
        vector[vector[int]] scc()
from libc.stdio cimport getchar, printf
cdef inline int read():
    cdef int b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: return c
        c = c * 10 + b
cdef int n = read(), m = read(), a, b, i, j
cdef scc_graph *g = new scc_graph(n)
for i in range(m):
    a = read()
    b = read()
    g.add_edge(a, b)
cdef vector[vector[int]] res = g.scc()
m = res.size()
printf('%d', m)
for i in range(m):
    m = res[i].size()
    printf('\n%d', m)
    for j in range(m): printf(' %d', res[i][j])
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve