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: Wrong Answer

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)
	for i in range(x):
		print(len(DAG[i]), *DAG[i])




if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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] == 2: 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] == 2: 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: Wrong Answer

Solution code:
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)
for uu in group:
    print(len(uu),end=" ")
    print(*uu)

Submission status: Wrong Answer

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:
          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: Wrong Answer

Solution code:
import networkx as nx

N,M = map(int,input().split())
G = nx.DiGraph()

for i in range(M):
  a,b = map(int,input().split())
  G.add_edge(a,b)
  
scc = list(nx.strongly_connected_components(G))
print(len(scc))
for cc in reversed(scc):
  print(len(cc),*cc)

Submission status: Wrong Answer

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 reversed(G1[a]):
                if seen[b]: continue
                todo.append(~b)
                todo.append(b)
        else:
          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: Wrong Answer

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 dfs(a0):
    global order
    todo = [~a0, a0]
    while todo:
        a = todo.pop()
        if a >= 0:
            seen[a] = 1
            for b in reversed(G1[a]):
                if seen[b]: continue
                todo.append(~b)
                todo.append(b)
        else:
          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: Wrong Answer

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 dfs(a0):
    global order
    todo = [~a0, a0]
    while todo:
        a = todo.pop()
        if a >= 0:
            seen[a] = 1
            for b in reversed(G1[a]):
                if seen[b]: continue
                todo.append(~b)
                todo.append(b)
        else:
          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: Wrong Answer

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

# strongly connected component
def scc(n,es):
    visited=[0]*n
    postorder=[]
    es_rev=[[] for i in range(n)]
    for i in range(n):
        for e in es[i]:
            es_rev[e].append(i)
    stack=[]
    for i in range(n):
        if visited[i]!=0:
            continue
        stack.append(i)
        while stack:
            s=stack.pop()
            if es[s]!=[]:
                g=es[s].pop()
                if visited[g]==0:
                    stack.append(g)
            if not es[s]:
                visited[s]=1
                postorder.append(s)
    visited=[0]*n
    out=[]
    while postorder:
        j=postorder.pop()
        if visited[j]==1:
            continue
        tmp=[j]
        visited[j]=1
        for e in es_rev[j]:
            if visited[e]==0:
                tmp.append(e)
                visited[e]=1
        out.append(tmp)
    return out

out=scc(n,es)

print(len(out))
for arr in out:
    print(len(arr), *arr)

Submission status: Wrong Answer

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

# strongly connected component
def scc(n,es):
    visited=[0]*n
    postorder=[]
    es_rev=[[] for i in range(n)]
    for i in range(n):
        for e in es[i]:
            es_rev[e].append(i)
    stack=[]
    for i in range(n):
        if visited[i]!=0:
            continue
        stack.append(i)
        while stack:
            s=stack.pop()
            if es[s]!=[]:
                g=es[s].pop()
                if visited[g]==0:
                    stack.append(g)
            if not es[s]:
                visited[s]=1
                postorder.append(s)
    visited=[0]*n
    out=[]
    while postorder:
        j=postorder.pop()
        if visited[j]==1:
            continue
        tmp=[j]
        visited[j]=1
        for e in es_rev[j]:
            if visited[e]==0:
                tmp.append(e)
                visited[e]=1
        out.append(tmp)
    return out

out=scc(n,es)

for arr in out:
    print(len(arr), *arr)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
e_in = [[] for _ in range(N)]
e_out = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    e_out[a].append(b)
    e_in[b].append(a)


visited = [0] * N
order = []
for i in range(N):
    if visited[i]:
        continue
    visited[i] = 1
    node = [~i, i]
    while node:
        s = node.pop()
        if s < 0:
            order.append(~s)
            continue
        for t in e_out[s]:
            if visited[t]:
                continue
            visited[t] = 1
            node.append(~t)
            node.append(t)

visited = [0] * N
comp = 0
for i in reversed(order):
    if visited[i]:
        continue
    comp += 1
    visited[i] = comp
    node = [i]
    while node:
        s = node.pop()
        for t in e_in[s]:
            if visited[t]:
                continue
            visited[t] = comp
            node.append(t)

scc = [[] for _ in range(comp)]
for i, k in enumerate(visited, start=0):
    scc[k-1].append(i)

print(comp)
for s in scc:
    print(len(s), end=" ")
    print(*s, sep=" ")

Submission status: Wrong Answer

Solution code:
import sys
def SCC(G):
  D=[]
  U=[1]*len(G)
  Z=[]
  for x in range(len(G)):
    if U[x]:
      U[x]=0
      Z.append((x,1))
      for i in range(len(G[x])):
        if U[G[x][i]]:
          Z.append((G[x][i],0))
          U[G[x][i]]=0
      while len(Z):
        if Z[-1][1]:
          D.append(Z[-1][0])
          del Z[-1]
        else:
          x=Z[-1][0]
          del Z[-1]
          Z.append((x,1))
          for i in range(len(G[x])):
            if U[G[x][i]]:
              Z.append((G[x][i],0))
              U[G[x][i]]=0
  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)
  for x in range(len(G)-1,-1,-1):
    x=D[x]
    if U[x]:
      R.append([x])
      U[x]=0
      for i in range(len(GR[x])):
        if U[GR[x][i]]:
          Z.append(GR[x][i])
          U[GR[x][i]]=0
      while len(Z):
        x=Z[-1]
        del Z[-1]
        R[-1].append(x)
        for i in range(len(GR[x])):
          if U[GR[x][i]]:
            Z.append(GR[x][i])
            U[GR[x][i]]=0
  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: Wrong Answer

Solution code:
import sys
def SCC(G):
  D=[]
  C=[len(G)-1]
  U=[1]*len(G)
  Z=[]
  for x in range(len(G)):
    if U[x]:
      U[x]=0
      Z.append((x,1))
      for i in range(len(G[x])):
        if U[G[x][i]]:
          Z.append((G[x][i],0))
          U[G[x][i]]=0
      while len(Z):
        if Z[-1][1]:
          D.append(Z[-1][0])
          del Z[-1]
        else:
          x=Z[-1][0]
          del Z[-1]
          Z.append((x,1))
          for i in range(len(G[x])):
            if U[G[x][i]]:
              Z.append((G[x][i],0))
              U[G[x][i]]=0
  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)
  for i in range(len(G)-1,-1,-1):
    if U[D[i]]:
      x=D[i]
      R.append([])
      R[-1].append(x)
      U[x]=0
      for i in range(len(GR[x])):
        if U[GR[x][i]]:
          Z.append(GR[x][i])
      while len(Z):
        x=Z[-1]
        del Z[-1]
        U[x]=0
        R[-1].append(x)
        for i in range(len(GR[x])):
          if U[GR[x][i]]:
            Z.append(GR[x][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: Wrong Answer

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    def dfs(links, s, checked, postorder):
        n = len(links)
        d = 1
        while d <= n:
            d <<= 1

        q = [s]
        checked[s] = 1
        while q:
            v = q.pop()
            if v < d:
                q.append(v | d)
                for u in links[v]:
                    if checked[u] == 0:
                        q.append(u)
                        checked[u] = 1
            else:
                postorder.append(v ^ d)
        return

    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':
    # noinspection PyUnresolvedReferences
    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)

Submission status: Wrong Answer

Solution code:
import sys
import networkx as nx

n, m = map(int, sys.stdin.buffer.readline().split())
mp = map(int, sys.stdin.buffer.read().split())
G = nx.DiGraph()
G.add_edges_from(zip(mp, mp))
sccs = list(nx.strongly_connected_components(G))
print(len(sccs))
for scc in reversed(sccs):
    print(len(scc), *scc)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]

def dfs(v):
    global last_ptr
    SEEN[v] = 1
    for next_v in G1[v]:
      if SEEN[next_v]:continue
      dfs(next_v)
    last_order[v] = last_ptr
    last_ptr += 1

def dfs2(v,res):
    seen[v] = 1
    res.append(v)
    for next_v in G2[v]:
      if last_order[next_v] > last_order[v] or last_order[next_v] == -1:continue
      if seen[next_v]:continue
      dfs2(next_v,res)
    return res
  
def toposort(inc, out):
    S = {i for i, c in enumerate(inc) if c == 0}
    L = []
    while S:
        n = S.pop()
        L.append(n)
        for m in out[n]:
            inc[m] -= 1
            if inc[m] == 0:
                S.add(m)
    return L

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)
  
inorder = list(zip(*sorted(enumerate([len(G2[i]) for i in range(N)]),reverse=True)))[0]

SEEN = [0]*N
scc = {}
uf = UnionFind(N)
for i in inorder:
  if SEEN[i]:continue
  last_order=[-1]*N
  last_ptr = 0
  dfs(i)
  order = list(zip(*sorted(enumerate(last_order),key=lambda x:x[1],reverse=True)))[0]
  seen = [0]*N
  for j in order:
    if last_order[j]==-1:break
    if seen[j]:continue
    res = dfs2(j,[])
    if len(res)>1:
      for i in range(len(res)-1):
        v1,v2 = res[i:i+2]
        uf.unite(v1,v2)
    scc[uf.find(res[0])] = res

G3 = [[] for _ in range(N)]
inc = [0]*N
for v1 in scc.keys():
  for v2 in scc[v1]:
    if v1 != v2: uf.unite(v1,v2)

for c in scc.keys():
  for v1 in scc[c]:
    for v2 in G1[v1]:
      if not uf.same(v1,v2):
        v1,v2 = map(uf.find,(v1,v2))
        G3[v1].append(v2)
        inc[v2] += 1
        
L = toposort(inc, G3)
print(len(scc))
for c in L:
  if uf.d[c] < 0:
    print(len(scc[c]),*scc[c])

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


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

    from collections import deque

    # compressed[v]: 縮約後のグラフで縮約前のvが属する頂点
    # num: 縮約後のグラフの頂点数
    def SCC(adj, adj_rev):
        N = len(adj) - 1
        seen = [0] * (N + 1)
        compressed = [0] * (N + 1)
        order = []

        for v0 in range(1, N + 1):
            if seen[v0]:
                continue
            st = deque()
            st.append(v0)
            while st:
                v = st.pop()
                if v < 0:
                    order.append(-v)
                else:
                    if seen[v]:
                        continue
                    seen[v] = 1
                    st.append(-v)
                    for u in adj[v]:
                        st.append(u)

        seen = [0] * (N + 1)
        num = 0
        for v0 in reversed(order):
            if seen[v0]:
                continue
            num += 1
            st = deque()
            st.append(v0)
            seen[v0] = 1
            compressed[v0] = num
            while st:
                v = st.pop()
                for u in adj_rev[v]:
                    if seen[u]:
                        continue
                    seen[u] = 1
                    compressed[u] = num
                    st.append(u)

        return num, compressed

    # 縮約後のグラフを構築
    # 先にSCC()を実行してnum, compressedを作っておく
    def construct(adj, num, compressed):
        N = len(adj) - 1
        adj_compressed = [set() for _ in range(num + 1)]
        for v in range(1, N + 1):
            v_cmp = compressed[v]
            for u in adj[v]:
                u_cmp = compressed[u]
                if v_cmp != u_cmp:
                    adj_compressed[v_cmp].add(u_cmp)
        return adj_compressed

    N, M = map(int, input().split())
    adj = [set() for _ in range(N+1)]
    adj_rev = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        adj[a+1].add(b+1)
        adj_rev[b+1].add(a+1)

    num, compressed = SCC(adj, adj_rev)
    ans = [[] for _ in range(num+1)]
    for v in range(1, N+1):
        ans[compressed[v]].append(v-1)
    for i in range(1, num+1):
        line = [len(ans[i])] + ans[i]
        print(*line)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import io
import os


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
N, M = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(M)]

from collections import defaultdict

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v]

# https://networkx.github.io/documentation/stable/_modules/networkx/algorithms/components/strongly_connected.html
def scc(G):
    preorder = {}
    lowlink = {}
    scc_found = {}
    scc_queue = []
    i = 0     # Preorder counter
    ans = []
    for source in G:
        if source not in scc_found:
            queue = [source]
            while queue:
                v = queue[-1]
                if v not in preorder:
                    i = i + 1
                    preorder[v] = i
                done = 1
                v_nbrs = G[v]
                for w in v_nbrs:
                    if w not in preorder:
                        queue.append(w)
                        done = 0
                        break
                if done == 1:
                    lowlink[v] = preorder[v]
                    for w in v_nbrs:
                        if w not in scc_found:
                            if preorder[w] > preorder[v]:
                                lowlink[v] = min([lowlink[v], lowlink[w]])
                            else:
                                lowlink[v] = min([lowlink[v], preorder[w]])
                    queue.pop()
                    if lowlink[v] == preorder[v]:
                        scc_found[v] = True
                        scc = {v}
                        while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
                            k = scc_queue.pop()
                            scc_found[k] = True
                            scc.add(k)
                        ans.append(scc)
                    else:
                        scc_queue.append(v)
    return ans


SCC = list(scc(graph))

DEBUG = False
print(len(SCC))
if DEBUG:
    seen = set()
for comp in reversed(SCC):
    print(len(comp), *comp)
    if DEBUG:
        for u in comp:
            for v in graph[u]:
                assert v not in seen
        seen.update(comp)

Submission status: Wrong Answer

Solution code:
import io
import os


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
N, M = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(M)]

from collections import defaultdict

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v]

# https://networkx.github.io/documentation/networkx-1.10/_modules/networkx/algorithms/components/strongly_connected.html#strongly_connected_components
def strongly_connected_components(G):
    """Generate nodes in strongly connected components of graph.

    Parameters
    ----------
    G : NetworkX Graph
        An directed graph.

    Returns
    -------
    comp : generator of sets
        A generator of sets of nodes, one for each strongly connected
        component of G.

    Raises
    ------
    NetworkXNotImplemented:
        If G is undirected.

    Examples
    --------
    Generate a sorted list of strongly connected components, largest first.

    >>> G = nx.cycle_graph(4, create_using=nx.DiGraph())
    >>> G.add_cycle([10, 11, 12])
    >>> [len(c) for c in sorted(nx.strongly_connected_components(G),
    ...                         key=len, reverse=True)]
    [4, 3]

    If you only want the largest component, it's more efficient to
    use max instead of sort.

    >>> largest = max(nx.strongly_connected_components(G), key=len)

    See Also
    --------
    connected_components,
    weakly_connected_components

    Notes
    -----
    Uses Tarjan's algorithm with Nuutila's modifications.
    Nonrecursive version of algorithm.

    References
    ----------
    .. [1] Depth-first search and linear graph algorithms, R. Tarjan
       SIAM Journal of Computing 1(2):146-160, (1972).

    .. [2] On finding the strongly connected components in a directed graph.
       E. Nuutila and E. Soisalon-Soinen
       Information Processing Letters 49(1): 9-14, (1994)..

    """
    preorder = {}
    lowlink = {}
    scc_found = {}
    scc_queue = []
    i = 0  # Preorder counter
    for source in G:
        if source not in scc_found:
            queue = [source]
            while queue:
                v = queue[-1]
                if v not in preorder:
                    i = i + 1
                    preorder[v] = i
                done = 1
                v_nbrs = G[v]
                for w in v_nbrs:
                    if w not in preorder:
                        queue.append(w)
                        done = 0
                        break
                if done == 1:
                    lowlink[v] = preorder[v]
                    for w in v_nbrs:
                        if w not in scc_found:
                            if preorder[w] > preorder[v]:
                                lowlink[v] = min([lowlink[v], lowlink[w]])
                            else:
                                lowlink[v] = min([lowlink[v], preorder[w]])
                    queue.pop()
                    if lowlink[v] == preorder[v]:
                        scc_found[v] = True
                        scc = {v}
                        while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
                            k = scc_queue.pop()
                            scc_found[k] = True
                            scc.add(k)
                        yield scc
                    else:
                        scc_queue.append(v)


SCC = list(strongly_connected_components(graph))

DEBUG = False
print(len(SCC))
if DEBUG:
    seen = set()
for comp in reversed(SCC):
    print(len(comp), *comp)
    if DEBUG:
        for u in comp:
            for v in graph[u]:
                assert v not in seen
        seen.update(comp)

Submission status: Wrong Answer

Solution code:
import sys

sys.path.append("/home/contestant/.local/lib/python3.8/site-packages")

import networkx as nx

import io
import os


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
N, M = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(M)]

graph = nx.DiGraph()
for u, v in edges:
    graph.add_edge(v, u)


if False:
    import matplotlib.pyplot as plt

    nx.draw_networkx(graph)
    plt.show()

DEBUG = False
if DEBUG:
    N = 1000
    M = N - 1
    if True:
        graph = nx.generators.random_graphs.gnm_random_graph(N, M, directed=True)
    else:
        graph = nx.MultiDiGraph()
        for i in range(1, N):
            graph.add_edge(i, i + 1)
    assert len(graph) == N
    assert graph.size() == M
    # print("done gen", file=sys.stderr)

SCC = list(nx.algorithms.components.strongly_connected_components(graph))
# SCC = list(nx.algorithms.components.strongly_connected_components_recursive(graph)) # maximum recursion depth exceeded
# SCC = list(nx.algorithms.components.kosaraju_strongly_connected_components(graph)) # Terrible perf


print(len(SCC))
if DEBUG:
    seen = set()
for comp in SCC:
    print(len(comp), *comp)
    if DEBUG:
        for u, v in graph.edges:
            if v in seen:
                assert u in seen
        seen.update(comp)