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:
from collections import deque

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 = [0] * self.n
        order = []
        for s in range(self.n):
            if group[s]: continue
            stack = deque([s])
            group[s] = -1
            while stack:
                node = stack.pop()
                for adj in self.graph[node]:
                    if group[adj]: continue
                    group[adj] = -1
                    stack.append(node)
                    stack.append(adj)
                    break
                else:
                    order.append(node)
        cnt = 0
        for s in order[::-1]:
            if group[s] != -1: continue
            stack = deque([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, g in enumerate(group):
            res[g].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)

Submission status: Accepted

Solution code:
class DiGraph:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.rev = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]

    def add_edge(self, fr, to):
        self.graph[fr].append(to)
        self.rev[to].append(fr)
        self.deg[to] += 1

    def scc_ids(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 scc(self):
        group, count = self.scc_ids()

        scc = [[] for _ in range(count)]
        for i, k in enumerate(group):
            scc[k].append(i)

        return scc


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

dg = DiGraph(N)

for i in range(M):
    dg.add_edge(*list(map(int, input().split())))

scc = dg.scc()

print(len(scc))
for c in scc:
    print(len(c), ' '.join(map(str, c)))

Submission status: Accepted

Solution code:
#-------最強ライブラリSCC(Python) ver25252------
import sys
sys.setrecursionlimit(1000000)

class scc_graph:
  # n 頂点数
  def __init__(s, n): 
    s._n = n
    s.g = {}
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): 
    if frm in s.g: s.g[frm].append(to)
    else: s.g[frm] = [to]

  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    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)
      if v in s.g:
        for to in s.g[v]:
          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

  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  def scc(s):
    group_num, ids = s.scc_ids()
    counts = [0] * group_num
    for x in ids: counts[x] += 1
    groups = [[] for _ in range(group_num)]
    for i in range(s._n):
      groups[ids[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 = [tuple(map(int, input().split())) for _ in range(m)]

  g = scc_graph(n)

  for u, v in ab:
    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()

Submission status: Accepted

Solution code:
#-------最強ライブラリSCC(Python) ver25252------
import sys
sys.setrecursionlimit(1000000)

class scc_graph:
  # n 頂点数
  def __init__(s, n): 
    s._n = n
    s.g = {}
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): 
    if frm in s.g: s.g[frm].append(to)
    else: s.g[frm] = [to]

  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    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)
      if v in s.g:
        for to in s.g[v]:
          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

  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  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


#-------最強ライブラリここまで------

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

Submission status: Accepted

Solution code:
#-------最強ライブラリSCC(Python) ver25252------
import sys
sys.setrecursionlimit(1000000)

class scc_graph:
  # n 頂点数
  def __init__(s, n): 
    s._n = n
    s.g = {}
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): 
    if frm in s.g: s.g[frm].append(to)
    else: s.g[frm] = [to]

  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    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)
      if v in s.g:
        for to in s.g[v]:
          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]

  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  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()

Submission status: Accepted

Solution code:
#-------最強ライブラリSCC(Python) ver25252------
class scc_graph:
  # n 頂点数
  def __init__(s, n): 
    s._n = n
    s.g = {}
    s.rg = {}
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): 
    if frm in s.g: s.g[frm].append(to)
    else: s.g[frm] = [to]
    if to in s.rg: s.rg[to].append(frm)
    else: s.rg[to] = [frm]

  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    def dfs(v):
      stack = [v]
      while stack:
        t = stack[-1]
        vis[t] = True
        if t not in s.g:
          vs.append(stack.pop())
          continue
        for i in s.g[t]:
          if not vis[i]:
            stack.append(i)
            break
        else:
          vs.append(stack.pop())

    def rdfs(v, n):
      stack = [v]
      vis[v] = True
      ids[v] = n
      while stack:
        t = stack.pop()
        vis[t] = True
        if t not in s.rg: continue
        for i in s.rg[t]:
          if not vis[i]:
            ids[i] = n
            stack.append(i)

    vis = [False] * s._n 
    vs = []
    ids = [-1] * s._n
    for i in range(s._n):
      if not vis[i]:
        dfs(i)
    group_num = 0
    vis = [False] * s._n 
    for i in vs[::-1]:
      if not vis[i]:
        rdfs(i, group_num)
        group_num += 1
    return group_num, ids 

  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  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

#-------最強ライブラリここまで------

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

Submission status: Accepted

Solution code:
#-------最強ライブラリSCC(Python) ver25252------
class scc_graph:
  # n 頂点数
  def __init__(s, n): 
    s._n = n
    s.edge = [s.component() for i in range(n)]
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): 
    s.edge[frm].add_go(to)
    s.edge[to].add_rgo(frm)

  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    def dfs(v):
      stack = [v]
      while stack:
        t = stack.pop()
        vis[t] = True
        for i in s.edge[t].go:
          if not vis[i]:
            stack.append(t)
            stack.append(i)
            break
        else:
          vs.append(t)

    def rdfs(v, n):
      stack = [v]
      vis[v] = True
      ids[v] = n
      while stack:
        t = stack.pop()
        vis[t] = True
        for i in s.edge[t].rgo:
          if not vis[i]:
            ids[i] = n
            stack.append(i)

    vis = [False] * s._n 
    vs = []
    ids = [-1] * s._n
    for i in range(s._n):
      if not vis[i]:
        dfs(i)
    group_num = 0
    vis = [False] * s._n 
    for i in vs[::-1]:
      if not vis[i]:
        rdfs(i, group_num)
        group_num += 1
    return group_num, ids 

  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  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 component:
    def __init__(s):
      s.go = []
      s.rgo = []
    def add_go(s, to):
      s.go.append(to)
    def add_rgo(s, frm):
      s.rgo.append(frm)

#-------最強ライブラリここまで------

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

Submission status: Accepted

Solution code:
#-------最強ライブラリSCC(Python) ver25252------
class scc_graph:
  # n 頂点数
  def __init__(s, n): 
    s._n = n
    s.g = {}
    s.rg = {}
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): 
    if frm in s.g: s.g[frm].append(to)
    else: s.g[frm] = [to]
    if to in s.rg: s.rg[to].append(frm)
    else: s.rg[to] = [frm]

  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    def dfs(v):
      stack = [v]
      while stack:
        t = stack.pop()
        vis[t] = True
        if t not in s.g:
          vs.append(t)
          continue
        for i in s.g[t]:
          if not vis[i]:
            stack.append(t)
            stack.append(i)
            break
        else:
          vs.append(t)

    def rdfs(v, n):
      stack = [v]
      vis[v] = True
      ids[v] = n
      while stack:
        t = stack.pop()
        vis[t] = True
        if t not in s.rg: continue
        for i in s.rg[t]:
          if not vis[i]:
            ids[i] = n
            stack.append(i)

    vis = [False] * s._n 
    vs = []
    ids = [-1] * s._n
    for i in range(s._n):
      if not vis[i]:
        dfs(i)
    group_num = 0
    vis = [False] * s._n 
    for i in vs[::-1]:
      if not vis[i]:
        rdfs(i, group_num)
        group_num += 1
    return group_num, ids 

  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  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

#-------最強ライブラリここまで------

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

Submission status: Accepted

Solution code:
#-------最強ライブラリSCC(Python) ver25252------
class scc_graph:
  # n 頂点数
  def __init__(s, n): 
    s._n = n
    s.g = [[] for _ in range(n)]
    s.rg = [[] for _ in range(n)]
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): 
    s.g[frm].append(to)
    s.rg[to].append(frm)

  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    def dfs(v):
      stack = [v]
      while stack:
        t = stack.pop()
        vis[t] = True
        for i in s.g[t]:
          if not vis[i]:
            stack.append(t)
            stack.append(i)
            break
        else:
          vs.append(t)

    def rdfs(v, n):
      stack = [v]
      vis[v] = True
      ids[v] = n
      while stack:
        t = stack.pop()
        vis[t] = True
        for i in s.rg[t]:
          if not vis[i]:
            ids[i] = n
            stack.append(i)

    vis = [False] * s._n 
    vs = []
    ids = [-1] * s._n
    for i in range(s._n):
      if not vis[i]:
        dfs(i)
    group_num = 0
    vis = [False] * s._n 
    for i in vs[::-1]:
      if not vis[i]:
        rdfs(i, group_num)
        group_num += 1
    return group_num, ids 

  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  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

#-------最強ライブラリここまで------

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

Submission status: Accepted

Solution code:
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 = [0] * self.n
        order = []
        for s in range(self.n):
            if group[s]: continue
            stack = [s]
            group[s] = -1
            while stack:
                node = stack.pop()
                for adj in self.graph[node]:
                    if group[adj]: continue
                    group[adj] = -1
                    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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#-------最強ライブラリSCC(Python) ver25252------

import copy
import sys
sys.setrecursionlimit(1000000)

class csr:
  # start 頂点iまでの頂点が、矢元として現れた回数
  # elist 矢先のリストを矢元の昇順にしたもの
  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:
  # n 頂点数
  def __init__(s, n): 
    s._n = n
    s.edges = []
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): s.edges.append(s.edge(frm, to))

  # グループの個数と各頂点のグループidを返す
  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]

  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  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()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class Graph(): #directed
    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)