Problem:


Score : 100 points

Problem Statement

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

Constraints

1 \leq N \leq 500,000

1 \leq M \leq 500,000

0 \leq a_i, b_i < N

Input

Input is given from Standard Input in the following format:

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

Output

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

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

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

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

Sample Input 1

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

Sample Output 1

4
1 5
2 4 1
1 2
2 3 0



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


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

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def inverse(N, mod):
	return (pow(N, mod - 2, mod))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

#強連結成分の個数と、それぞれの頂点がどの成分に属すかを返す
def scc(N, G, Grev):
	order = []
	visit = [0] * N
	group = [None] * N #あるノードが強連結の何番目のグループに含まれるか
	def dfs(node):
		visit[node] = 1
		for i in G.graph[node]:
			if not visit[i]:
				dfs(i)
		order.append(node)

	def dfs_rev(node, num):
		group[node] = num
		visit[node] = 1
		for i in Grev.graph[node]:
			if not visit[i]:
				dfs_rev(i, num)

	#順方向のグラフ上でDFSを行い、帰りがけ順に頂点を記録
	for i in range(N):
		if not visit[i]:
			dfs(i)

	#逆方向のグラフ上で帰りが遅かった頂点から順にDFSを行い分解
	visit = [0] * N
	num = 0
	for i in reversed(order):
		if not visit[i]:
			dfs_rev(i, num)
			num += 1

	return num, group

#scc後のDAGを構築
def construct(N, G, num, group):
	DAG = [[] for i in range(num)]
	for i in range(N):
		itr = group[i]
		DAG[itr].append(i)

	return DAG

def getlist():
	return list(map(int, input().split()))


def main():
	N, M = getlist()
	G = Graph()
	Grev = Graph()
	for i in range(M):
		a, b = getlist()
		G.add_edge(a, b)
		Grev.add_edge(b, a)

	num, group = scc(N, G, Grev)

	DAG = construct(N, G, num, group)
	x = len(DAG)
	print(x)
	for i in range(x):
		print(len(DAG[i]), *DAG[i])




if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
def scc(E):
    n = len(E)
    iE = [[] for _ in range(n)]
    for i, e in enumerate(E):
        for v in e:
            iE[v].append(i)
    T = []
    done = [0] * n # 0 -> 1 -> 2
    ct = 0
    for i0 in range(n):
        if done[i0]: continue
        Q = [~i0, i0]
        while Q:
            i = Q.pop()
            if i < 0:
                if done[~i] == 2: continue
                done[~i] = 2
                T.append(~i)
                ct += 1
                continue
            if i >= 0:
                if done[i]: continue
                done[i] = 1
            for j in E[i]:
                if done[j]: continue
                Q.append(~j)
                Q.append(j)
    
    done = [0] * n
    SCC = []
    for i0 in T[::-1]:
        if done[i0]: continue
        L = []
        Q = [~i0, i0]
        while Q:
            i = Q.pop()
            if i < 0:
                if done[~i] == 2: continue
                done[~i] = 2
                L.append(~i)
                continue
            if i >= 0:
                if done[i]: continue
                done[i] = 1
            for j in iE[i]:
                if done[j]: continue
                Q.append(~j)
                Q.append(j)
        SCC.append(L)
    return SCC

N, M = map(int, input().split())
X = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    X[x].append(y)
S = scc(X)
print(len(S))
for s in S:
    print(*[len(s)] + s)

Submission status: Accepted

Solution code:
from operator import itemgetter
from itertools import *
from bisect import *
from collections import *
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def scc(to,ot):
    n=len(to)
    def dfs(u):
        for v in to[u]:
            if com[v]:continue
            com[v]=1
            dfs(v)
        top.append(u)

    top=[]
    com=[0]*n
    for u in range(n):
        if com[u]:continue
        com[u]=1
        dfs(u)

    def rdfs(u,k):
        for v in ot[u]:
            if com[v]!=-1:continue
            com[v]=k
            rdfs(v,k)

    com=[-1]*n
    k=0
    for u in top[::-1]:
        if com[u]!=-1:continue
        com[u]=k
        rdfs(u,k)
        k+=1

    return k,com

n,m=MI()
to=[[] for _ in range(n)]
ot=[[] for _ in range(n)]
for _ in range(m):
    u,v=MI()
    to[u].append(v)
    ot[v].append(u)
k,com=scc(to,ot)
group=[[] for _ in range(k)]
for u,g in enumerate(com):
    group[g].append(u)
    
print(k)
for uu in group:
    print(len(uu),end=" ")
    print(*uu)

Submission status: Accepted

Solution code:
class SCC:
  '''
  SCC class with non-recursive DFS.
  '''
  def __init__(self,N):
    self.N = N
    self.G1 = [[] for _ in range(N)]
    self.G2 = [[] for _ in range(N)]
  
  def add_edge(self,a,b):
    self.G1[a].append(b)
    self.G2[b].append(a)
    
  def scc(self):
    self.seen = [0]*self.N
    self.postorder=[-1]*self.N
    self.order = 0
    for i in range(self.N):
      if self.seen[i]:continue
      self._dfs(i)

    self.seen = [0]*self.N
    scclist = []
    for i in self._argsort(self.postorder,reverse=True):
      if self.seen[i]:continue
      cc = self._dfs2(i)
      scclist.append(cc)
    
    return scclist
    
  def _argsort(self,arr,reverse=False):
    shift = self.N.bit_length()+2
    tmp = sorted([arr[i]<<shift | i for i in range(len(arr))],reverse=reverse)
    mask = (1<<shift) - 1
    return [tmp[i] & mask for i in range(len(arr))]
  
  def _dfs(self,v0):
    todo = [~v0, v0]
    while todo:
      v = todo.pop()
      if v >= 0:
        self.seen[v] = 1
        for next_v in self.G1[v]:
          if self.seen[next_v]: continue
          todo.append(~next_v)
          todo.append(next_v)
      else:
        if self.postorder[~v] == -1:
          self.postorder[~v] = self.order
          self.order += 1
    return
  
  def _dfs2(self,v):
    todo = [v]
    self.seen[v] = 1
    cc = [v]
    while todo:
      v = todo.pop()
      for next_v in self.G2[v]:
        if self.seen[next_v]: continue
        self.seen[next_v] = 1
        todo.append(next_v)
        cc.append(next_v)
    return cc

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)
  scclist = scc.scc()
  print(len(scclist))
  for cc in scclist:
    print(len(cc),*cc)
    
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
class SCC:
  '''
  SCC class with non-recursive DFS.
  '''
  def __init__(self,N):
    self.N = N
    self.G1 = [[] for _ in range(N)]
    self.G2 = [[] for _ in range(N)]
  
  def add_edge(self,a,b):
    self.G1[a].append(b)
    self.G2[b].append(a)
    
  def scc(self):
    self.seen = [0]*self.N
    self.postorder=[-1]*self.N
    self.order = 0
    for i in range(self.N):
      if self.seen[i]:continue
      self._dfs(i)

    self.seen = [0]*self.N
    scclist = []
    for i in self._argsort(self.postorder,reverse=True):
      if self.seen[i]:continue
      cc = self._dfs2(i)
      scclist.append(cc)
    
    return scclist
    
  def _argsort(self,arr,reverse=False):
    shift = self.N.bit_length()+2
    tmp = sorted([arr[i]<<shift | i for i in range(len(arr))],reverse=reverse)
    mask = (1<<shift) - 1
    return [tmp[i] & mask for i in range(len(arr))]
  
  def _dfs(self,v0):
    todo = [~v0, v0]
    while todo:
      v = todo.pop()
      if v >= 0:
        self.seen[v] = 1
        for next_v in self.G1[v]:
          if self.seen[next_v]: continue
          todo.append(~next_v)
          todo.append(next_v)
      else:
        if self.postorder[~v] == -1:
          self.postorder[~v] = self.order
          self.order += 1
    return
  
  def _dfs2(self,v):
    todo = [v]
    self.seen[v] = 1
    cc = [v]
    while todo:
      v = todo.pop()
      for next_v in self.G2[v]:
        if self.seen[next_v]: continue
        self.seen[next_v] = 1
        todo.append(next_v)
        cc.append(next_v)
    return cc

def main():
  N,M = map(int,input().split())
  sc = SCC(N)
  for i in range(M):
    a,b=map(int,input().split())
    sc.add_edge(a,b)
  scclist = sc.scc()
  print(len(scclist))
  for cc in scclist:
    print(len(cc),*cc)
    
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
def argsort(arr, reverse=False, shift=20):
    N = len(arr)
    tmp=[0]*N
    for i in range(N):
        tmp[i] = (arr[i] << shift) | i
    tmp = sorted(tmp,reverse=reverse)
    out=[0]*N
    mask = (1<<shift) - 1
    for j in range(N):
        i = tmp[j] & mask
        out[j] = i
    return out

def dfs(G1,a0,seen,postorder,order):
    todo = [~a0, a0]
    while todo:
        a = todo.pop()
        if a >= 0:
            seen[a] = 1
            for b in G1[a]:
                if seen[b]: continue
                todo.append(~b)
                todo.append(b)
        else:
          if postorder[~a] == -1:
            postorder[~a] = order
            order += 1
    return seen,postorder,order
  
def dfs2(G2,v,seen):
    todo = [v]
    seen[v] = 1
    cc = [v]
    while todo:
        v = todo.pop()
        for next_v in G2[v]:
            if seen[next_v]: continue
            seen[next_v] = 1
            todo.append(next_v)
            cc.append(next_v)
    return cc,seen
  
def scc(G1,G2):
  N = len(G1)
  seen = [0]*N
  postorder=[-1]*N
  order = 0
  for i in range(N):
    if seen[i]:continue
    seen,postorder,order = dfs(G1,i,seen,postorder,order)

  seen = [0]*N
  scclist = []
  for i in argsort(postorder,reverse=True):
    if seen[i]:continue
    cc,seen = dfs2(G2,i,seen)
    scclist.append(cc)
  return scclist

def main():
  N,M = map(int,input().split())
  G1 = [[] for _ in range(N)]
  G2 = [[] for _ in range(N)]
  for i in range(M):
    a,b=map(int,input().split())
    G1[a].append(b)
    G2[b].append(a)
  scclist = scc(G1,G2)
  print(len(scclist))
  for cc in scclist:
    print(len(cc),*cc)
    
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
G1 = [[] for _ in range(N)]
G2 = [[] for _ in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  G1[a].append(b)
  G2[b].append(a)
  
def argsort(arr, reverse=False, shift=20):
    N = len(arr)
    tmp=[0]*N
    for i in range(N):
        tmp[i] = (arr[i] << shift) | i
    tmp = sorted(tmp,reverse=reverse)
    out=[0]*N
    mask = (1<<shift) - 1
    for j in range(N):
        i = tmp[j] & mask
        out[j] = i
    return out

def dfs(a0,seen,postorder,order):
    todo = [~a0, a0]
    while todo:
        a = todo.pop()
        if a >= 0:
            seen[a] = 1
            for b in G1[a]:
                if seen[b]: continue
                todo.append(~b)
                todo.append(b)
        else:
          if postorder[~a] == -1:
            postorder[~a] = order
            order += 1
    return seen,postorder,order
  
def dfs2(v,seen):
    todo = [v]
    seen[v] = 1
    cc = [v]
    while todo:
        v = todo.pop()
        for next_v in G2[v]:
            if seen[next_v]: continue
            seen[next_v] = 1
            todo.append(next_v)
            cc.append(next_v)
    return cc,seen
  
def scc(G1,G2):
  N = len(G1)
  seen = [0]*N
  postorder=[-1]*N
  order = 0
  for i in range(N):
    if seen[i]:continue
    seen,postorder,order = dfs(i,seen,postorder,order)

  seen = [0]*N
  scclist = []
  for i in argsort(postorder,reverse=True):
    if seen[i]:continue
    cc,seen = dfs2(i,seen)
    scclist.append(cc)
  return scclist

def main():
  scclist = scc(G1,G2)
  print(len(scclist))
  for cc in scclist:
    print(len(cc),*cc)
    
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
G1 = [[] for _ in range(N)]
G2 = [[] for _ in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  if a == b:continue
  G1[a].append(b)
  G2[b].append(a)

def dfs(a0):
    global order
    todo = [~a0, a0]
    while todo:
        a = todo.pop()
        if a >= 0:
            seen[a] = 1
            for b in G1[a]:
                if seen[b]: continue
                todo.append(~b)
                todo.append(b)
        else:
          if postorder[~a] == -1:
            postorder[~a] = order
            order += 1
    return
  
def dfs2(v):
    todo = [v]
    seen[v] = 1
    cc = [v]
    while todo:
        v = todo.pop()
        for next_v in G2[v]:
            if seen[next_v]: continue
            seen[next_v] = 1
            todo.append(next_v)
            cc.append(next_v)
    return cc
  
seen = [0]*N
postorder=[-1]*N
order = 0
for i in range(N):
  if seen[i]:continue
  dfs(i)

seen = [0]*N
scc = []
for i,_ in sorted(enumerate(postorder),key=lambda x:x[1],reverse=True):
  if seen[i]:continue
  cc = dfs2(i)
  scc.append(cc)
  
print(len(scc))
for cc in scc:
  print(len(cc),*cc)

Submission status: Accepted

Solution code:
# Reference: https://mathtrain.jp/kyorenketsu#:~:text=%E5%BC%B7%E9%80%A3%E7%B5%90%E6%88%90%E5%88%86%E5%88%86%E8%A7%A3%E3%81%A8,%E9%80%A3%E7%B5%90%E6%88%90%E5%88%86%EF%BC%89%E3%81%AB%E5%B1%9E%E3%81%97%E3%81%BE%E3%81%99%E3%80%82
# Reference: https://tjkendev.github.io/procon-library/python/graph/scc.html
# Strongly Connected Components
# This is made for "AtCoderLibraryPracticeContest/G-SCC"
from sys import stdin, setrecursionlimit
setrecursionlimit(10**9)
input = stdin.buffer.readline

# n = the number of nodes
# m = the number of edges
n, m = map(int, input().split())

edges = [[] for _ in range(n)]
reversed_edges = [[] for _ in range(n)]
for _ in range(m):
    i, j = map(int, input().split())
    edges[i].append(j)
    reversed_edges[j].append(i)

def scc(n, edges, reversed_edges):
    order = []
    seen = [True] * n

    def dfs(node):
        seen[node] = False
        for i in edges[node]:
            if seen[i]:
                dfs(i)
        order.append(node)

    for i in range(n):
        if seen[i]:
            dfs(i)

    groups = []
    seen = [True] * n
    for start in reversed(order):
        if seen[start]:
            ### DFS
            seen[start] = False
            todo = [start]
            group = [start]
            while len(todo) > 0:
                node = todo.pop(-1)
                for j in reversed_edges[node]:
                    if seen[j]:
                        seen[j] = False
                        todo.append(j)
                        group.append(j)
            ###
            group.reverse()
            groups.append(group)

    return groups

groups = scc(n, edges, reversed_edges)
print(len(groups))
for group in groups:
    print(len(group), ' '.join(map(str, group)))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

sys.setrecursionlimit(5*10**5)

N,M = map(int,input().split())
edge = [[] for i in range(N)]
rev_edge = [[] for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    edge[a].append(b)
    rev_edge[b].append(a)

seen = [False]*N
stop = []

def dfs(v):
    for nv in edge[v]:
        if not seen[nv]:
            seen[nv]=True
            dfs(nv)
    stop.append(v)

for i in range(N):
    if not seen[i]:
        seen[i] = True
        dfs(i)

seen = [False]*N

def scc():
    res = []
    connect = []
    def rev_dfs(v):
        for nv in rev_edge[v]:
            if not seen[nv]:
                connect.append(nv)
                seen[nv]=True
                rev_dfs(nv)

    while stop:
        while stop and seen[stop[-1]]:
            stop.pop()
        if not stop:
            break
        connect = [stop[-1]]
        seen[stop[-1]] = True
        rev_dfs(stop[-1])
        res.append(connect)
    return res

res = scc()
print(len(res))
for L in res:
    print(len(L),*L)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
es = [[] for _ in range(n)]
for i in range(m):
    a,b=map(int, input().split())
    es[a].append(b)
# Strongly Connected Component
def scc(n_node,es): # DFSを2回行う
    esinv = [[] for _ in range(n_node)]
    for i in range(n_node):
        for e in es[i]:
            esinv[e].append(i)
    used = [False]*n_node
    dim = [len(es[i]) for i in range(n_node)]
    order = []
    for st in range(n_node): # DFS 1回目, postorderを求める
        if not used[st]:
            stack = [(st, 0)] # [(index, 既に辿ったエッジの数)]
            while stack:
                now, i = stack.pop() 
                if not i and used[now]:
                    continue
                else:
                    used[now] = True
                    if i < dim[now]: # nowから延びるエッジを辿りきってない
                        stack.append((now,i+1))
                        stack.append((es[now][i],0))
                    else: # nowから延びる全てのエッジを辿った
                        order.append(now)
    res = [-1]*n_node # 各ノードが所属するグループのidを保存
    used = [False]*n_node 
    cnt = -1 # idカウンター
    for st in order[::-1]:  # DFS 2回目, postorderの逆順から
        if not used[st]:    # 逆向き矢印を辿って通れるノードを記録していく
            cnt += 1
            stack = [st]
            res[st] = cnt
            used[st] = True
            while stack:
                now = stack.pop()
                for e in esinv[now]:
                    if not used[e]:
                        used[e] = True
                        res[e] = cnt
                        stack.append(e)
    n_group = cnt+1
    components = [[] for _ in range(n_group)]
    for i in range(n_node):
        components[res[i]].append(i)
    return res, components # 各ノードの所属グループid, 各グループの構成ノード

res, comp=scc(n,es)
row=max(res)+1
print(row)
for i in range(row):
    length = len(comp[i])
    print(length, *comp[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
es = [[] for _ in range(n)]
for i in range(m):
    a,b=map(int, input().split())
    es[a].append(b)

# Strongly Connected Component
def scc(n_node,es): # DFSを2回行う
    esinv = [[] for _ in range(n_node)]
    for i in range(n_node):
        for e in es[i]:
            esinv[e].append(i)
    used = [False]*n_node
    dim = [len(es[i]) for i in range(n_node)]
    order = []
    for st in range(n_node): # DFS 1回目, postorderを求める
        if not used[st]:
            stack = [(st, 0)] # [(index, 既に辿ったエッジの数)]
            while stack:
                now, i = stack.pop() 
                if not i and used[now]:
                    continue
                else:
                    used[now] = True
                    if i < dim[now]: # nowから延びるエッジを辿りきってない
                        stack.append((now,i+1))
                        stack.append((es[now][i],0))
                    else: # nowから延びる全てのエッジを辿った
                        order.append(now)
    res = [-1]*n_node # 各ノードが所属するグループのidを保存
    used = [False]*n_node 
    cnt = -1 # idカウンター
    for st in order[::-1]:  # DFS 2回目, postorderの逆順から
        if not used[st]:    # 逆向き矢印を辿って通れるノードを記録していく
            cnt += 1
            stack = [st]
            res[st] = cnt
            used[st] = True
            while stack:
                now = stack.pop()
                for e in esinv[now]:
                    if not used[e]:
                        used[e] = True
                        res[e] = cnt
                        stack.append(e)
    n_group = cnt+1
    components = [[] for _ in range(n_group)]
    for i in range(n_node):
        components[res[i]].append(i)
    return components # 各グループのノード

comp=scc(n,es)
row=len(comp)
print(row)
for i in range(row):
    length = len(comp[i])
    print(length, *comp[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
es = [[] for _ in range(n)]
for i in range(m):
    a,b=map(int, input().split())
    es[a].append(b)

# strongly connected component
def scc(n_node,es): # DFSを2回行う
    esinv = [[] for _ in range(n_node)]
    for i in range(n_node):
        for e in es[i]:
            esinv[e].append(i)
    used = [False]*n_node
    dim = [len(es[i]) for i in range(n_node)]
    order = []
    for st in range(n_node): # DFS 1回目, postorderを求める
        if not used[st]:
            stack = [(st, 0)] # [(index, 既に辿ったエッジの数)]
            while stack:
                now, i = stack.pop() 
                if not i and used[now]:
                    continue
                else:
                    used[now] = True
                    if i < dim[now]: # nowから延びるエッジを辿りきってない
                        stack.append((now,i+1))
                        stack.append((es[now][i],0))
                    else: # nowから延びる全てのエッジを辿った
                        order.append(now)
    res = [-1]*n_node # 各ノードが所属するグループのidを保存
    used = [False]*n_node 
    cnt = -1 # idカウンター
    for st in order[::-1]:  # DFS 2回目, postorderの逆順から
        if not used[st]:    # 逆向き矢印を辿って通れるノードを記録していく
            cnt += 1
            stack = [st]
            res[st] = cnt
            used[st] = True
            while stack:
                now = stack.pop()
                for e in esinv[now]:
                    if not used[e]:
                        used[e] = True
                        res[e] = cnt
                        stack.append(e)
    n_group = cnt+1
    components = [[] for _ in range(n_group)]
    for i in range(n_node):
        components[res[i]].append(i)
    return res, components

res,compo=scc(n,es)
# print(res,compo)

row=max(res)+1

print(row)
for i in range(row):
    length = len(compo[i])
    print(length, *compo[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
es = [[] for _ in range(n)]
for i in range(m):
    a,b=map(int, input().split())
    es[a].append(b)

# strongly connected component
def scc(es): # DFSを2回行う
    n_node = len(es)
    esinv = [[] for _ in range(n_node)]
    for i in range(n_node):
        for e in es[i]:
            esinv[e].append(i)
    used = [False]*n_node
    dim = [len(es[i]) for i in range(n_node)]
    order = []
    for st in range(n_node): # DFS 1回目, postorderを求める
        if not used[st]:
            stack = [(st, 0)] # [(index, 既に辿ったエッジの数)]
            while stack:
                now, i = stack.pop() 
                if not i and used[now]:
                    continue
                else:
                    used[now] = True
                    if i < dim[now]: # nowから延びるエッジを辿りきってない
                        stack.append((now,i+1))
                        stack.append((es[now][i],0))
                    else: # nowから延びる全てのエッジを辿った
                        order.append(now)
    res = [-1]*n_node # 各ノードが所属するグループのidを保存
    used = [False]*n_node 
    cnt = -1 # idカウンター
    for st in order[::-1]:  # DFS 2回目, postorderの逆順から
        if not used[st]:    # 逆向き矢印を辿って通れるノードを記録していく
            cnt += 1
            stack = [st]
            res[st] = cnt
            used[st] = True
            while stack:
                now = stack.pop()
                for e in esinv[now]:
                    if not used[e]:
                        used[e] = True
                        res[e] = cnt
                        stack.append(e)
    n_group = cnt+1
    components = [[] for _ in range(n_group)]
    for i in range(n_node):
        components[res[i]].append(i)
    return res, components

res,compo= scc(es)
# print(res,compo)

row=max(res)+1

print(row)
for i in range(row):
    length = len(compo[i])
    print(length, *compo[i])

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    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)

        return res, components
    
    N,M=MI()
    adj=[[]for _ in range(N)]
    for i in range(M):
        a,b=MI()
        adj[a].append(b)
        
    res,compo= scc(adj)
    
    M=max(res)+1
    
    print(M)
    for i in range(M):
        length = len(compo[i])
        print(' '.join(map(str, [length]+compo[i])))
    
    

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
def SCC(G):
  D=[]
  C=[len(G)-1]
  U=[1]*len(G)
  def DFS(x):
    if U[x]:
      U[x]=0
      for i in range(len(G[x])):
        DFS(G[x][i])
      D.append(x)
  
  for i in range(len(G)):
    if U[i]:
      DFS(i)
  GR=[[] for i in range(len(G))]
  for i in range(len(G)):
    for j in range(len(G[i])):
      GR[G[i][j]].append(i)
  R=[]
  U=[1]*len(G)
  def DFSR(x):
    if U[x]:
      R[-1].append(x)
      U[x]=0
      for i in range(len(GR[x])):
        DFSR(GR[x][i])
  
  for i in range(len(G)-1,-1,-1):
    if U[D[i]]:
      R.append([])
      DFSR(D[i])
  return R

S=sys.stdin.readlines()
N,M=map(int,S[0].split())
G=[[] for i in range(N)]
a,b=0,0
for i in range(M):
  a,b=map(int,S[i+1].split())
  G[a].append(b)
P=SCC(G)
print(len(P))
for i in range(len(P)):
  print(*([len(P[i])]+P[i]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
def SCC(G):
  D=[]
  C=[len(G)-1]
  U=[1]*len(G)
  def DFS(x):
    if U[x]:
      U[x]=0
      for i in range(len(G[x])):
        DFS(G[x][i])
      D.append(x)
  
  for i in range(len(G)):
    if U[i]:
      DFS(i)
  GR=[[] for i in range(len(G))]
  for i in range(N):
    for j in range(len(G[i])):
      GR[G[i][j]].append(i)
  R=[]
  U=[1]*len(G)
  def DFSR(x):
    if U[x]:
      R[-1].append(x)
      U[x]=0
      for i in range(len(GR[x])):
        DFSR(GR[x][i])
  
  for i in range(len(G)-1,-1,-1):
    if U[D[i]]:
      R.append([])
      DFSR(D[i])
  return R

S=sys.stdin.readlines()
N,M=map(int,S[0].split())
G=[[] for i in range(N)]
a,b=0,0
for i in range(M):
  a,b=map(int,S[i+1].split())
  G[a].append(b)
P=SCC(G)
print(len(P))
for i in range(len(P)):
  print(*([len(P[i])]+P[i]))