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: Runtime Error

Solution code:
from collections import deque
class csr:
    def __init__(self,N,edges):
        self.start = [0]*(N+1)
        self.elist = [0]*len(edges)
        for e in edges:
            self.start[e[0]+1] += 1
        for i in range(1,N+1):
            self.start[i] += self.start[i-1] 
        counter = self.start[:]
        for e in edges:
            self.elist[counter[e[0]]] = e[1]
            counter[e[0]] += 1

class scc_graph:
    def __init__(self,N):
        self.N = N
        self.edges = []
    
    def add_edge(self,v,w):
        self.edges.append((v,w))

    def scc_ids(self):
        g = csr(self.N,self.edges)
        now_ord = group_num = 0
        visited = deque()
        low = [0]*self.N
        order = [-1]*self.N
        ids = [0]*self.N
        parent = [-1]*self.N
        for i in range(self.N):
            if order[i] == -1:
                stack = deque()
                stack.append(i)
                stack.append(i)
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        low[v] = order[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 order[to] == -1:
                                stack.append(to)
                                stack.append(to)
                                parent[to] = v
                            else:
                                low[v] = min(low[v],order[to])
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[u] = self.N
                                ids[u] = group_num
                                if u == v:
                                    break
                            group_num += 1
                        if parent[v] != -1:
                            low[parent[v]] = min(low[parent[v]],low[v])
        for i,x in enumerate(ids):
            ids[i] = group_num-1-x

        return group_num,ids
    
    def scc(self):
        group_num,ids = self.scc_ids()
        groups = [[] for _ in range(group_num)]
        for i,x in enumerate(ids):
            groups[x].append(i)
        return groups
    
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
N,M = map(int,readline().split())
ab = list(map(int,read().split()))
sg = scc_graph

it = iter(ab)
for a,b in zip(it,it):
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(str(len(group))+' '+' '.join(map(str,group)))

Submission status: Runtime Error

Solution code:
from collections import deque
class csr:
    def __init__(self,N,edges):
        self.start = [0]*(N+1)
        self.elist = [0]*len(edges)
        for e in edges:
            self.start[e[0]+1] += 1
        for i in range(1,N+1):
            self.start[i] += self.start[i-1] 
        counter = self.start[:]
        for e in edges:
            self.elist[counter[e[0]]] = e[1]
            counter[e[0]] += 1
        print(self.start,self.elist)

class scc_graph:
    def __init__(self,N):
        self.N = N
        self.edges = []
    
    def add_edge(self,v,w):
        self.edges.append((v,w))

    def scc_ids(self):
        g = csr(self.N,self.edges)
        now_ord = group_num = 0
        visited = deque()
        low = [0]*self.N
        order = [-1]*self.N
        ids = [0]*self.N
        parent = [-1]*self.N
        for i in range(self.N):
            if order[i] == -1:
                stack = deque()
                stack.append(i)
                stack.append(i)
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        low[v] = order[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 order[to] == -1:
                                stack.append(to)
                                stack.append(to)
                                parent[to] = v
                            else:
                                low[v] = min(low[v],order[to])
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[u] = self.N
                                ids[u] = group_num
                                if u == v:
                                    break
                            group_num += 1
                        if parent[v] != -1:
                            low[parent[v]] = min(low[parent[v]],low[v])
            print(ids)
        for i,x in enumerate(ids):
            ids[i] = group_num-1-x

        return group_num,ids
    
    def scc(self):
        group_num,ids = self.scc_ids()
        print(ids)
        groups = [[] for _ in range(group_num)]
        for i,x in enumerate(ids):
            groups[x].append(i)
        return groups
    
import sys
input = sys.stdin.buffer.readline
N,M = map(int,input().split())
sg = scc_graph(N)
for i in range(M):
    a,b = map(int,input().split())
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(str(len(group))+' '+' '.join(map(str,group)))

Submission status: Runtime Error

Solution code:
import sys
range = xrange
input = raw_input

def find_SCC(coupl):
    SCC, S, P = [], [], []
    depth = [0] * len(coupl)
 
    stack = list(range(len(coupl)))
    while stack:
        node = stack.pop()
        if node < 0:
            d = depth[~node] - 1
            if P[-1] > d:
                SCC.append(S[d:])
                del S[d:], P[-1]
                for node in SCC[-1]:
                    depth[node] = -1
        elif depth[node] > 0:
            while P[-1] > depth[node]:
                P.pop()
        elif depth[node] == 0:
            S.append(node)
            P.append(len(S))
            depth[node] = len(S)
            stack.append(~node)
            stack += coupl[node]
    return SCC[::-1]

inp = [int(x) for x in sys.stdin.read().split()]; ii = 0

n = inp[ii]; ii += 1
m = inp[ii]; ii += 1

coupl = [[] for _ in range(n)]
for _ in range(m):
  	u = inp[ii] - 1; ii += 1
    v = inp[ii] - 1; ii += 1
    coupl[u].append(v)

SCC = find_SCC(coupl)
out = [len(SCC)]
for scc in SCC:
	out.append(len(scc))
    for node in scc:
    	out.append(node + 1)
print ' '.join(str(x) for x in out)

Submission status: Runtime Error

Solution code:
def scc(N, G, RG):
    order = []
    used = [0]*N
    group = [None]*N
    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)
    def rdfs(s, col):
        group[s] = col
        used[s] = 1
        for t in RG[s]:
            if not used[t]:
                rdfs(t, col)
    for i in range(N):
        if not used[i]:
            dfs(i)
    used = [0]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs(s, label)
            label += 1
    return label, group

# 縮約後のグラフを構築
def construct(N, G, label, group):
    G0 = [set() for i in range(label)]
    GP = [[] for i in range(label)]
    for v in range(N):
        lbs = group[v]
        for w in G[v]:
            lbt = group[w]
            if lbs == lbt:
                continue
            G0[lbs].add(lbt)
        GP[lbs].append(v)
    return G0, GP

N,M = list(map(int, input().split()))
G = [[] for i in range(N)]
RG = [[] for i in range(N)]

for i in range(M):
    A,B=list(map(int, input().split()))
    G[A].append(B)
    RG[B].append(A)

label,group = scc(N, G, RG)
G0,GP = construct(N, G, label, group)
print(label)
for G in GP:
    print(len(G),*G)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8[:, :], i8[:], i8[:], i8[:], i8[:], i8[:], i8, i8, i8, i8),
      cache=True)
def scc_dfs(N, G, idx, low, ord, ids, visited, now_ord, group_num, vis_i, v):
    low[v] = ord[v] = now_ord
    now_ord += 1
    visited[vis_i], vis_i = v, vis_i + 1
    for e in range(idx[v], idx[v + 1]):
        to = G[e, 1]
        if ord[to] == -1:
            now_ord, group_num, vis_i = \
                scc_dfs(N, G, idx, low, ord, ids,
                        visited, now_ord, group_num,
                        vis_i, to)
            low[v] = min(low[v], low[to])
        else:
            low[v] = min(low[v], ord[to])
    if low[v] == ord[v]:
        while True:
            u, vis_i = visited[vis_i - 1], vis_i - 1
            ord[u] = N
            ids[u] = group_num
            if u == v:
                break
        group_num += 1
    return now_ord, group_num, vis_i


@njit((i8, i8[:, :]), cache=True)
def scc(N, G):
    idx = np.searchsorted(G[:, 0], np.arange(N + 1))
    low = np.zeros(N, np.int64)
    ord = np.zeros(N, np.int64) - 1
    now_ord = 0
    group_num = 0
    visited, vis_i = np.empty(N, np.int64), 0
    ids = np.zeros(N, np.int64)
    for v in range(N):
        if ord[v] == -1:
            now_ord, group_num, vis_i = \
                scc_dfs(N, G, idx, low, ord, ids,
                        visited, now_ord, group_num,
                        vis_i, v)
    return group_num, group_num - ids - 1

@njit((i8, i8, i8[:]), cache=True)
def main(N, D, XY):
    # X を True として、two sat に帰着する
    X, Y = XY[::2], XY[1::2]
    G, g = np.empty((4 * N * N, 2), np.int64), 0
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            if abs(X[i] - X[j]) < D:
                # i True implies j False
                G[g], g = (i, j + N), g + 1
            if abs(X[i] - Y[j]) < D:
                # i True implies j True
                G[g], g = (i, j), g + 1
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            if abs(Y[i] - X[j]) < D:
                # i False implies j False
                G[g], g = (i + N, j + N), g + 1
            if abs(Y[i] - Y[j]) < D:
                # i False implies j True
                G[g], g = (i + N, j), g + 1
    G = G[:g]
    n_comp, comp = scc(N + N, G)
    ans = np.empty(N, np.int64)
    for i in range(N):
        if comp[i] < comp[i + N]:
            ans[i] = Y[i]
        elif comp[i] > comp[i + N]:
            ans[i] = X[i]
        else:
            print('No')
            return
    print('Yes')
    for x in ans:
        print(x)

N, D = map(int, readline().split())
XY = np.array(read().split(), np.int64)

main(N, D, XY)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8[:, :], i8[:], i8[:], i8[:], i8[:], i8[:], i8, i8, i8, i8),
      cache=True)
def scc_dfs(N, G, idx, low, ord, ids, visited, now_ord, group_num, vis_i, v):
    low[v] = ord[v] = now_ord
    now_ord += 1
    visited[vis_i], vis_i = v, vis_i + 1
    for e in range(idx[v], idx[v + 1]):
        to = G[e, 1]
        if ord[to] == -1:
            now_ord, group_num, vis_i = \
                scc_dfs(N, G, idx, low, ord, ids,
                        visited, now_ord, group_num,
                        vis_i, to)
            low[v] = min(low[v], low[to])
        else:
            low[v] = min(low[v], ord[to])
    if low[v] == ord[v]:
        while True:
            u, vis_i = visited[vis_i - 1], vis_i - 1
            ord[u] = N
            ids[u] = group_num
            if u == v:
                break
        group_num += 1
    return now_ord, group_num, vis_i


@njit((i8, i8[:, :]), cache=True)
def scc(N, G):
    idx = np.searchsorted(G[:, 0], np.arange(N + 1))
    low = np.zeros(N, np.int64)
    ord = np.zeros(N, np.int64) - 1
    now_ord = 0
    group_num = 0
    visited, vis_i = np.empty(N, np.int64), 0
    ids = np.zeros(N, np.int64)
    for v in range(N):
        if ord[v] == -1:
            now_ord, group_num, vis_i = \
                scc_dfs(N, G, idx, low, ord, ids,
                        visited, now_ord, group_num,
                        vis_i, v)
    return group_num, group_num - ids - 1

@njit((i8, i8, i8[:]), cache=True)
def main(N, D, XY):
    # X を True として、two sat に帰着する
    X, Y = XY[::2], XY[1::2]
    G, g = np.empty((4 * N * N, 2), np.int64), 0
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            if abs(X[i] - X[j]) < D:
                # i True implies j False
                G[g], g = (i, j + N), g + 1
            if abs(X[i] - Y[j]) < D:
                # i True implies j True
                G[g], g = (i, j), g + 1
    for i in range(N):
        for j in range(N):
            if abs(Y[i] - X[j]) < D:
                # i False implies j False
                G[g], g = (i + N, j + N), g + 1
            if abs(Y[i] - Y[j]) < D:
                # i False implies j True
                G[g], g = (i + N, j), g + 1
    G = G[:g]
    n_comp, comp = scc(N + N, G)
    ans = np.empty(N, np.int64)
    for i in range(N):
        if comp[i] < comp[i + N]:
            ans[i] = Y[i]
        elif comp[i] > comp[i + N]:
            ans[i] = X[i]
        else:
            print('No')
            return
    print('Yes')
    for x in ans:
        print(x)

N, D = map(int, readline().split())
XY = np.array(read().split(), np.int64)

main(N, D, XY)

Submission status: Runtime Error

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder__scc_code = """
import copy
import typing


class CSR:
    def __init__(
            self, n: int, edges: typing.List[typing.Tuple[int, int]]) -> None:
        self.start = [0] * (n + 1)
        self.elist = [0] * len(edges)

        for e in edges:
            self.start[e[0] + 1] += 1

        for i in range(1, n + 1):
            self.start[i] += self.start[i - 1]

        counter = copy.deepcopy(self.start)
        for e in edges:
            self.elist[counter[e[0]]] = e[1]
            counter[e[0]] += 1


class SCCGraph:
    '''
    Reference:
    R. Tarjan,
    Depth-First Search and Linear Graph Algorithms
    '''

    def __init__(self, n: int) -> None:
        self._n = n
        self._edges = []

    def num_vertices(self) -> int:
        return self._n

    def add_edge(self, from_vertex: int, to_vertex: int) -> None:
        self._edges.append((from_vertex, to_vertex))

    def scc_ids(self) -> typing.Tuple[int, typing.List[int]]:
        g = CSR(self._n, self._edges)
        now_ord = 0
        group_num = 0
        visited = []
        low = [0] * self._n
        order = [-1] * self._n
        ids = [0] * self._n

        def dfs(v: int) -> None:
            nonlocal now_ord
            nonlocal group_num
            nonlocal visited
            nonlocal low
            nonlocal order
            nonlocal ids

            low[v] = now_ord
            order[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 order[to] == -1:
                    dfs(to)
                    low[v] = min(low[v], low[to])
                else:
                    low[v] = min(low[v], order[to])

            if low[v] == order[v]:
                while True:
                    u = visited[-1]
                    visited.pop()
                    order[u] = self._n
                    ids[u] = group_num
                    if u == v:
                        break
                group_num += 1

        for i in range(self._n):
            if order[i] == -1:
                dfs(i)

        for i in range(self._n):
            ids[i] = group_num - 1 - ids[i]

        return (group_num, ids)

    def scc(self) -> typing.List[typing.List[int]]:
        ids = self.scc_ids()
        group_num = ids[0]
        counts = [0] * group_num
        for x in ids[1]:
            counts[x] += 1
        groups = [[] for _ in range(group_num)]
        for i in range(self._n):
            groups[ids[1][i]].append(i)

        return groups
"""

atcoder._scc = types.ModuleType('atcoder._scc')
exec(_atcoder__scc_code, atcoder._scc.__dict__)


_atcoder_scc_code = """
import typing

# import atcoder._scc


class SCCGraph:
    def __init__(self, n: int) -> None:
        self._internal = atcoder._scc.SCCGraph(n)

    def add_edge(self, from_vertex: int, to_vertex: int) -> None:
        n = self._internal.num_vertices()
        assert 0 <= from_vertex < n
        assert 0 <= to_vertex < n
        self._internal.add_edge(from_vertex, to_vertex)

    def scc(self) -> typing.List[typing.List[int]]:
        return self._internal.scc()
"""

atcoder.scc = types.ModuleType('atcoder.scc')
exec(_atcoder_scc_code, atcoder.scc.__dict__)
atcoder.scc.__dict__['atcoder'] = atcoder
atcoder.scc.__dict__['atcoder._scc'] = atcoder._scc
SCCGraph = atcoder.scc.SCCGraph

# https://atcoder.jp/contests/practice2/tasks/practice2_b

import sys

# from atcoder.scc import SCCGraph


def main() -> None:
    n, m = map(int, sys.stdin.readline().split())
    g = SCCGraph(n)

    for i in range(m):
        u, v = map(int, sys.stdin.readline().split())
        g.add_edge(u, v)

    scc = g.scc()

    print(len(scc))
    for v in scc:
        print(len(v), end='')
        for x in v:
            print(f' {x}', end='')
        print('')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll=long long;
using Graph=vector<vector<int>>;
using pp=pair<ll,pair<ll,ll>>;
#define MAX 1000000
#define MOD 1000000007
#define INF 1000000000000000000

int main(){
  int N,M;
  cin>>N>>M;
  scc_graph G(N);
  for(int i=0;i<M;i++){
    int a,b;
    cin>>a>>b;
    G.add_edge(a,b);
  }

  vector<vector<int>> A=G.scc();
  cout<<A.size()<<endl;
  for(int i=0;i<A.size();i++){
    cout<<A[i].size();
    for(int j=0;j<A[i].size();j++){
      cout<<" "<<A[i][j];
    }
    cout<<endl;
  }
}

Submission status: Runtime Error

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


def dfs_numbering(i, M, V, ANS, cnt, v):
    V[i] = v
    for x in M[i]:
        if V[x] == -1:
            cnt = dfs_numbering(x, M, V, ANS, cnt, v)
    ANS[i] = cnt
    return cnt + 1

class scc():
    def __init__(self, n):
        self.n = n
        self.M = [[] for i in range(n)]
        self.IM = [[] for i in range(n)]

    def add_edge(self, frm, to):
        self.M[frm].append(to)
        self.IM[to].append(frm)

    def scc_list(self):
        n = self.n
        V = [-1] * n
        ANS = [-1] * n

        for i in range(n):
            if V[i] == -1:
                dfs_numbering(i, self.M, V, ANS, 0, 0)

        ANS1 = [[ANS[i], i] for i in range(n)]
        ANS1.sort(reverse=True)

        V = [-1] * n
        ANS = [-1] * n
        v = 0
        for i in range(n):
            if V[ANS1[i][1]] == -1:
                dfs_numbering(ANS1[i][1], self.IM, V, ANS, 0, v)
                v += 1

        FANS = [[] for i in range(v)]
        for i in range(n):
            FANS[V[i]].append(i)

        return FANS

S = scc(n)
for i in range(m):
    S.add_edge(C[i][0], C[i][1])
ANS = S.scc_list()

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

Submission status: Runtime Error

Solution code:

from collections import defaultdict


def scc(g):
    rg = defaultdict(list)
    V = set()
    for u, e in g.items():
        V.add(u)
        for v in e:
            V.add(v)
            rg[v].append(u)


    o = []
    done = set()
    def dfs(u):
        done.add(u)
        for v in g[u]:
            if v in done:
                continue
            dfs(v)
            done.add(v)
        # o[u] = len(o)
        o.append(u)

    for v in V:
        if v in done:
            continue
        dfs(v)

    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue
        done.add(u)
        s = [u]
        vv = []

        while s:
            u = s.pop()
            vv.append(u)
            for v in rg[u]:
                if v in done:
                    continue
                s.append(v)
                done.add(v)
        ans.append(vv)

    return ans


def atcoder_practice2_g():
    N, M = map(int, input().split())

    g = defaultdict(list)
    for _ in range(M):
        a, b = map(int, input().split())
        g[a].append(b)
    vv = scc(g)
    print(len(vv))
    for r in vv:
        print(len(r), *r)


def test():
    g = {
        1: [2],
        5: [2],
        2: [4, 3],
        3: [4, 7, 6],
        4: [5, 8],
        6: [9],
        7: [8],
        8: [9],
        9: [7, 10],
        10: []
    }

    vv = scc(g)
    for r in vv:
        print(r)


if __name__ == "__main__":
    # test()
    atcoder_practice2_g()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

class StrongConnections:
  def __init__(self, n, root = None):
    self.n = n
    self.root = root
    self.e = [[] for _ in range(n + 1)]
    self.re = [[] for _ in range(n + 1)]
  def add_edge(self, fr, to):
    self.e[fr].append(to)
    self.re[to].append(fr)
  def SCC(self):
    n = self.n
    root = self.root
    self.stop = [0] * (n + 1)
    contv = []
    conttable = [0] * (n + 1)
    self.vis = [0] * (n + 1)
    self.z = 0
    if root == None:
      for i in range(1, n + 1):
        if self.vis[i]: continue
        self._dfs(i)
    else: self._dfs(root)
    t = [(self.stop[i], i) for i in range(1, n + 1)]
    self.vis = [0] * (n + 1)
    while len(t):
      _, i = t.pop()
      if self.vis[i]: continue
      contv.append([])
      contv[-1] += self._contractdfs(i)
    for i in range(len(contv)):
      a = contv[i]
      for x in a: conttable[x] = i
    return contv
  def _dfs(self, x):
    self.vis[x] = 1
    for y in self.e[x]:
      if self.vis[y]: continue
      self._dfs(y)
    self.stop[x] = self.z + 1
    self.z += 1
  def _contractdfs(self, x):
    self.vis[x] = 1
    res = [x]
    for y in self.re[x]:
      if self.vis[y]: continue
      res += self._contractdfs(y)
    return res

scc = StrongConnections(N - 1)
for _ in range(M):
  u, v = map(int, input().split())
  scc.add_edge(u, v)
sccres = scc.SCC()
print(len(sccres))
for res in sccres: print(len(res), *res)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
e=[[] for _ in range(n)]
e_rev=[[] for _ in range(n)]
for i in range(m):
    ai,bi=map(int, input().split())
    e[ai].append(bi)
    e_rev[bi].append(ai)

p_ord=[]
used=[0]*n
def dfs(v):
    used[v]=1
    for u in e[v]:
        if not used[u]:
            dfs(u)
    p_ord.append(v)
for i in range(n):
    if not used[i]:
        dfs(i)
compo = [0]*n
used=[0]*n
def dfs_rev(v,c):
    compo[v]=c
    used[v]=1
    for u in e_rev[v]:
        if not used[u]:
            dfs_rev(u,c)
cnt=0
for i in reversed(p_ord):
    if not used[i]:
        dfs_rev(i,cnt)
        cnt+=1
cc=[[] for _ in range(cnt+1)]
for i in range(n):
    cc[compo[i]].append(i)

print(len([cci for cci in cc if cci]))
for cci in cc:
    if cci:
        print(len(cci),*cci)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
e=[[] for _ in range(n)]
e_rev=[[] for _ in range(n)]
for i in range(m):
    ai,bi=map(int, input().split())
    e[ai].append(bi)
    e_rev[bi].append(ai)

p_ord=[]
used=[0]*n
def dfs(v):
    used[v]=1
    for u in e[v]:
        if not used[u]:
            dfs(u)
    p_ord.append(v)
for i in range(n):
    if not used[i]:
        dfs(i)
compo = [0]*n
used=[0]*n
def dfs_rev(v,c):
    compo[v]=c
    used[v]=1
    for u in e_rev[v]:
        if not used[u]:
            dfs_rev(u,c)
cnt=-1
for i in reversed(p_ord):
    cnt+=1##
    if not used[i]:
        dfs_rev(i,cnt)
        #cnt+=1
cc=[[] for _ in range(cnt)]
for i in range(n):
    cc[compo[i]].append(i)

print(len(cc))
for cci in cc:
    print(len(cci),*cci)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
e=[[] for _ in range(n)]
e_rev=[[] for _ in range(n)]
for i in range(m):
    ai,bi=map(int, input().split())
    e[ai].append(bi)
    e_rev[bi].append(ai)

p_ord=[]
used=[0]*n
def dfs(v):
    used[v]=1
    for u in e[v]:
        if not used[u]:
            dfs(u)
    p_ord.append(v)
for i in range(n):
    if not used[i]:
        dfs(i)
compo = [0]*n
used=[0]*n
def dfs_rev(v,c):
    compo[v]=c
    used[v]=1
    for u in e_rev[v]:
        if not used[u]:
            dfs_rev(u,c)
cnt=0
for i in reversed(p_ord):
    if not used[i]:
        dfs_rev(i,cnt)
        cnt+=1
cc=[[] for _ in range(cnt)]
for i in range(n):
    cc[compo[i]].append(i)

print(len(cc))
for cci in cc:
    print(len(cci),*cci)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
e=[[] for _ in range(n)]
e_rev=[[] for _ in range(n)]
for i in range(m):
    ai,bi=map(int, input().split())
    e[ai].append(bi)
    e_rev[bi].append(ai)

p_ord=[]
used=[0]*n
def dfs(v):
    used[v]=1
    for u in e[v]:
        if not used[u]:
            dfs(u)
    p_ord.append(v)
for i in range(n):
    if not used[i]:
        dfs(i)
compo = [0]*n
used=[0]*n
def dfs_rev(v,c):
    compo[v]=c
    used[v]=1
    for u in e_rev[v]:
        if not used[u]:
            dfs_rev(u,c)
cnt=0
for i in reversed(p_ord):
    if not used[i]:
        dfs_rev(i,cnt)
        cnt+=1
cc=[[] for _ in range(cnt)]
for i in range(n):
    cc[compo[i]].append(i)
print(len(cc))
for cci in cc:
    print(len(cci),*cci)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
e=[[] for _ in range(n)]
e_rev=[[] for _ in range(n)]
for i in range(m):
    ai,bi=map(int, input().split())
    e[ai].append(bi)
    e_rev[bi].append(ai)

p_ord=[]
used=[0]*n
def dfs(v):
    used[v]=1
    for u in e[v]:
        if not used[u]:
            dfs(u)
    p_ord.append(v)
for i in range(n):
    if not used[i]:
        dfs(i)
compo = [0]*n
used=[0]*n
def dfs_rev(v,c):
    compo[v]=c
    used[v]=1
    for u in e_rev[v]:
        if not used[u]:
            dfs_rev(u,c)
cnt=0
for i in reversed(p_ord):
    if not used[i]:
        dfs_rev(i,cnt)
        cnt+=1
cc=[[] for _ in range(cnt+1)]
for i in range(n):
    cc[compo[i]].append(i)
print(len(cc))
for cci in cc:
    print(len(cci),*cci)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N, M, *AB = map(int, open(0).read().split())

G = csr_matrix(([1] * M, (AB[::2], AB[1::2])))
K, labels = connected_components(G, connection='strong')

C = [[] for _ in range(K)]
for i, l in enumerate(labels):
    C[l].append(i)

print(K)
for c in reversed((C)):
    print(len(c), *c)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N, M, *AB = map(int, open(0).read().split())

G = csr_matrix(([1] * M, (AB[::2], AB[1::2])))
K, labels = connected_components(G, connection='strong')

C = [[] for _ in range(K)]
for i, l in enumerate(labels):
    C[l].append(i)

print(K)
for c in C:
    print(len(c), *c)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

sys.setrecursionlimit(5*10**5)

N,M = map(int,input().split())
edge = [[] for i in range(M)]
rev_edge = [[] for i in range(M)]
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: Runtime Error

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

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