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

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


if False:
    import matplotlib.pyplot as plt

    nx.draw_networkx(graph)
    plt.show()

if False:
    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


"""
Not sure why this isn't the correct topo order?
seen = set()
for comp in reversed(SCC):
    print(len(comp), *comp)
    for u, v in graph.edges:
        if v in seen:
            assert u in seen
    seen.update(comp)
"""

print(len(SCC))
condensation = nx.algorithms.components.condensation(graph, SCC)
for compId in nx.algorithms.dag.topological_sort(condensation):
    comp = SCC[compId]
    print(len(comp), *comp)

Submission status: Wrong Answer

Solution code:
import sys

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


import io
import os

import networkx as nx


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.MultiDiGraph(edges)

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))
for comp in reversed(SCC):  # TODO: check what order these are returned in
    print(len(comp), *comp)

Submission status: Wrong Answer

Solution code:
import io
import os

import networkx as nx


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.MultiDiGraph(edges)

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))
for comp in reversed(SCC):  # TODO: check what order these are returned in
    print(len(comp), *comp)

Submission status: Wrong Answer

Solution code:
import networkx as nx

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

if False:
    import matplotlib.pyplot as plt

    nx.draw_networkx(graph)
    plt.show()

SCC = list(
    nx.algorithms.components.strongly_connected_components(graph)
)
print(len(SCC))
for comp in reversed(SCC):
    print(len(comp), *comp)

Submission status: Wrong Answer

Solution code:
import networkx

N, M = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(M)]

graph = networkx.DiGraph(edges)
SCC = list(networkx.algorithms.components.kosaraju_strongly_connected_components(graph))
print(len(SCC))
for comp in SCC:
    print(len(comp), *comp)

Submission status: Wrong Answer

Solution code:
import networkx

N, M = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(M)]

graph = networkx.DiGraph(edges)
SCC = list(networkx.algorithms.components.strongly_connected_components(graph))
print(len(SCC))
for comp in SCC:
    print(len(comp), *comp)

Submission status: Wrong Answer

Solution code:
class Digraph:
    """重み[なし]有向グラフを生成する.

    """

    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:set() for v in vertex} #出近傍(vが始点)
        self.adjacent_in={v:set() for v in vertex} #入近傍(vが終点)

    #頂点の追加
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]=set()
                self.adjacent_out[v]=set()

                self.vertex_number+=1
                self.vertex.add(v)

    #辺の追加
    def add_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From].add(To)
        self.adjacent_in[To].add(From)

    #辺を除く
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To in self.adjacent_out[From]:
            self.adjacent_out[From].remove(To)
            self.adjacent_in[To].remove(From)
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    self.adjacent_in[u].remove(v)
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    self.adjacent_out[u].remove(v)
                    self.edge_number-=1
                del self.adjacent_in[v]

    #Walkの追加
    def add_walk(self,*walk):
        N=len(walk)
        for k in range(N-1):
            self.add_edge(walk[k],walk[k+1])

    #Cycleの追加
    def add_cycle(self,*cycle):
        self.add_walk(*cycle)
        self.add_edge(cycle[-1],cycle[0])

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.vertex

    #グラフに辺が存在するか否か
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #出次数
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    #入次数
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        pass

#Topologycal Sort
def Topological_Sort(D):
    from collections import deque

    X={v:D.in_degree(v) for v in D.vertex}
    Q=deque([v for v in D.vertex if X[v]==0])

    S=[]
    while Q:
        u=Q.pop()
        S.append(u)
        for v in D.adjacent_out[u]:
            X[v]-=1
            if X[v]==0:
                Q.append(v)

    return S

#強連結成分に分解
def Strongly_Connected_Component_Decomposition(D,Mode=0):
    """有向グラフDを強連結成分に分解

    Mode:
    0(Defalt)---各強連結成分の頂点のリスト
    1        ---各頂点が属している強連結成分の番号
    2        ---0,1の両方
    """
    import sys
    from collections import deque

    T={x:-1 for x in D.vertex}
    Q=deque([])

    def f(v):
        T[v]=0
        for w in D.adjacent_out[v]:
            if T[w]==-1:
                f(w)

        Q.append(v)
        T[v]=len(Q)
    x=D.vertex.pop()
    D.vertex.add(x)

    RT=sys.getrecursionlimit()
    sys.setrecursionlimit(3*10**5)
    for v in D.vertex:
        if T[v]==-1:
            f(v)
    sys.setrecursionlimit(RT)

    T={x:-1 for x in D.vertex}
    C=[]
    p=0

    for v in Q:
        if T[v]==-1:
            T[v]=p
            P=[v]
            R=deque([v])

            while R:
                u=R.popleft()
                for w in D.adjacent_out[u]:
                    if T[w]==-1:
                        T[w]=p
                        R.append(w)
                        P.append(w)
            C.append(P)
            p+=1

    C=C[::-1]
    if Mode==1:
        return T
    elif Mode==2:
        return (C,T)
    else:
        return C
#================================================
N,M=map(int,input().split())
D=Digraph(list(range(N)))

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

C=Strongly_Connected_Component_Decomposition(D)

X=[""]*(len(C))
for i in range(len(C)):
    X[i]="{} {}".format(len(C[i])," ".join(map(str,C[i])))

print(len(C))
print("\n".join(X))

Submission status: Wrong Answer

Solution code:
class Digraph:
    """重み[なし]有向グラフを生成する.

    """

    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:set() for v in vertex} #出近傍(vが始点)
        self.adjacent_in={v:set() for v in vertex} #入近傍(vが終点)

    #頂点の追加
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]=set()
                self.adjacent_out[v]=set()

                self.vertex_number+=1
                self.vertex.add(v)

    #辺の追加
    def add_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From].add(To)
        self.adjacent_in[To].add(From)

    #辺を除く
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To in self.adjacent_out[From]:
            self.adjacent_out[From].remove(To)
            self.adjacent_in[To].remove(From)
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    self.adjacent_in[u].remove(v)
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    self.adjacent_out[u].remove(v)
                    self.edge_number-=1
                del self.adjacent_in[v]

    #Walkの追加
    def add_walk(self,*walk):
        N=len(walk)
        for k in range(N-1):
            self.add_edge(walk[k],walk[k+1])

    #Cycleの追加
    def add_cycle(self,*cycle):
        self.add_walk(*cycle)
        self.add_edge(cycle[-1],cycle[0])

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.vertex

    #グラフに辺が存在するか否か
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #出次数
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    #入次数
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        pass

#Topologycal Sort
def Topological_Sort(D):
    from collections import deque

    X={v:D.in_degree(v) for v in D.vertex}
    Q=deque([v for v in D.vertex if X[v]==0])

    S=[]
    while Q:
        u=Q.pop()
        S.append(u)
        for v in D.adjacent_out[u]:
            X[v]-=1
            if X[v]==0:
                Q.append(v)

    return S

#強連結成分に分解
def Strongly_Connected_Component_Decomposition(D,Mode=0):
    """有向グラフDを強連結成分に分解

    Mode:
    0(Defalt)---各強連結成分の頂点のリスト
    1        ---各頂点が属している強連結成分の番号
    2        ---0,1の両方
    """
    import sys
    from collections import deque

    T={x:-1 for x in D.vertex}
    Q=deque([])

    def f(v):
        T[v]=0
        for w in D.adjacent_out[v]:
            if T[w]==-1:
                f(w)

        Q.append(v)
        T[v]=len(Q)
    x=D.vertex.pop()
    D.vertex.add(x)

    RT=sys.getrecursionlimit()
    sys.setrecursionlimit(3*10**5)
    for v in D.vertex:
        if T[v]==-1:
            f(v)
    sys.setrecursionlimit(RT)

    T={x:-1 for x in D.vertex}
    C=[]
    p=0

    for v in Q:
        if T[v]==-1:
            T[v]=p
            P=[v]
            R=deque([v])

            while R:
                u=R.popleft()
                for w in D.adjacent_out[u]:
                    if T[w]==-1:
                        T[w]=p
                        R.append(w)
                        P.append(w)
            C.append(P)
            p+=1

    C=C[::-1]
    if Mode==1:
        return T
    elif Mode==2:
        return (C,T)
    else:
        return C
#================================================
N,M=map(int,input().split())
D=Digraph(list(range(N)))

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

C=Strongly_Connected_Component_Decomposition(D)

X=[""]*(len(C))
for i in range(len(C)):
    X[i]="{} {}".format(len(C[i])," ".join(map(str,C[i])))

print(len(C)+1)
print("\n".join(X))

Submission status: Wrong Answer

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[:, :]), cache=True)
def scc(N, G):
    ind = np.searchsorted(G[:, 0], np.arange(N + 2))
    preorder = np.empty(N, np.int64)
    n = 0
    st = np.empty(N, np.int64)
    p = 0
    nxt = np.full(N + 1, -1, np.int64)

    for root in range(N):
        if nxt[root] != -1:
            continue
        st[p], p = root, p + 1
        while p:
            v = st[p - 1]
            if nxt[v] == -1:
                nxt[v] = ind[v]
            if nxt[v] == ind[v + 1]:
                preorder[n], n = v, n + 1
                p -= 1
                continue
            w = G[nxt[v], 1]
            nxt[v] += 1
            if nxt[w] != -1:
                continue
            st[p], p = w, p + 1
    Grev = G[:, :2][:, ::-1].copy()
    Grev = Grev[np.argsort(Grev[:, 0])]
    ind = np.searchsorted(Grev[:, 0], np.arange(N + 2))
    comp = np.zeros(N, np.int64)
    n_comp = 0
    for root in preorder[::-1]:
        if comp[root]:
            continue
        n_comp += 1
        comp[root] = n_comp
        st[p], p = root, p + 1
        while p:
            v, p = st[p - 1], p - 1
            for i in range(ind[v], ind[v + 1]):
                w = Grev[i, 1]
                if comp[w]:
                    continue
                comp[w] = n_comp
                st[p], p = w, p + 1
    return n_comp, comp

def main(N, G):
    n_comp, comp = scc(N, G)

N, M = map(int, readline().split())
AB = np.array(read().split(), np.int64).reshape(-1, 2)

AB = AB[np.argsort(AB[:, 0])]

main(N, AB)

Submission status: Wrong Answer

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[:, :]), cache=True)
def scc(N, G):
    ind = np.searchsorted(G[:, 0], np.arange(N + 2))
    preorder = np.empty(N, np.int64)
    n = 0
    st = np.empty(N, np.int64)
    p = 0
    nxt = np.full(N + 1, -1, np.int64)

    for root in range(N):
        if nxt[root] != -1:
            continue
        st[p], p = root, p + 1
        while p:
            v = st[p - 1]
            if nxt[v] == -1:
                nxt[v] = ind[v]
            if nxt[v] == ind[v + 1]:
                preorder[n], n = v, n + 1
                p -= 1
                continue
            w = G[nxt[v], 1]
            nxt[v] += 1
            if nxt[w] != -1:
                continue
            st[p], p = w, p + 1
    Grev = G[:, :2][:, ::-1].copy()
    Grev = Grev[np.argsort(Grev[:, 0])]
    ind = np.searchsorted(Grev[:, 0], np.arange(N + 2))
    comp = np.zeros(N, np.int64)
    n_comp = 0
    for root in preorder[::-1]:
        if comp[root]:
            continue
        n_comp += 1
        comp[root] = n_comp
        st[p], p = root, p + 1
        while p:
            v, p = st[p - 1], p - 1
            for i in range(ind[v], ind[v + 1]):
                w = Grev[i, 1]
                if comp[w]:
                    continue
                comp[w] = n_comp
                st[p], p = w, p + 1
    return n_comp, comp

def main(N, G):
    n_comp, comp = scc(N, G)
    ans = np.empty((N, 2), np.int64)
    ans[:, 0] = np.arange(N)
    ans[:, 1] = comp
    ans = ans[np.argsort(ans[:, 1])]
    idx = np.searchsorted(ans[:, 1], np.arange(n_comp + 2))
    print(n_comp)
    for c in range(1, n_comp + 1):
        print(c, *ans[idx[c]:idx[c + 1], 0])

N, M = map(int, readline().split())
AB = np.array(read().split(), np.int64).reshape(-1, 2)

AB = AB[np.argsort(AB[:, 0])]

main(N, AB)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def solve():
    def getStronglyConnectedComponents(adjList):
        numV = len(adjList)

        def dfs1_stack(vSt):
            stack = [vSt]
            useds[vSt] = True
            dones = [False] * numV
            while stack:
                vNow = stack[-1]
                if dones[vNow]:
                    vsInPostOrder.append(vNow)
                    stack.pop()
                else:
                    for v2 in adjList[vNow]:
                        if not useds[v2]:
                            stack.append(v2)
                            useds[v2] = True
                    dones[vNow] = True

        vsInPostOrder = []
        useds = [False] * numV
        for vSt in range(numV):
            if not useds[vSt]:
                dfs1_stack(vSt)

        adjListRev = [[] for _ in range(numV)]
        for v in range(numV):
            for v2 in adjList[v]:
                adjListRev[v2].append(v)

        def dfs2_stack(vSt, noSCC):
            stack = [vSt]
            useds[vSt] = True
            while stack:
                vNow = stack.pop()
                noSCCs[vNow] = noSCC
                for v2 in adjListRev[vNow]:
                    if not useds[v2]:
                        stack.append(v2)
                        useds[v2] = True

        noSCCs = [-1] * numV
        useds = [False] * numV
        noSCC = 0
        for vSt in reversed(vsInPostOrder):
            if not useds[vSt]:
                dfs2_stack(vSt, noSCC)
                noSCC += 1

        return noSCCs

    def getDAGbySCC(adjList, noSCCs):
        numV = len(adjList)
        numSCC = len(set(noSCCs))
        adjLDAG = [set() for _ in range(numSCC)]
        for v in range(numV):
            vc = noSCCs[v]
            for v2 in adjList[v]:
                vc2 = noSCCs[v2]
                if vc != vc2:
                    adjLDAG[vc].add(vc2)
        return adjLDAG

    def TopologicalSort(adjList):
        numV = len(adjList)
        indegs = [0] * numV
        for v in range(numV):
            for v2 in adjList[v]:
                indegs[v2] += 1
        anss = [v for v in range(numV) if indegs[v] == 0]
        Q = deque(anss)
        while Q:
            vNow = Q.popleft()
            for v2 in adjList[vNow]:
                indegs[v2] -= 1
                if indegs[v2] == 0:
                    anss.append(v2)
                    Q.append(v2)
        return anss


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

    noSCCs = getStronglyConnectedComponents(adjL)
    numSCC = len(set(noSCCs))

    SCCs = [[] for _ in range(numSCC)]
    for v in range(N):
        SCCs[noSCCs[v]].append(v)

    adjL2 = getDAGbySCC(adjL, noSCCs)

    vTopos = TopologicalSort(adjL2)

    ansss = []
    for v in vTopos:
        anss = [len(SCCs[v])] + SCCs[v]
        ansss.append(anss)

    print(numSCC)
    print('\n'.join([' '.join(map(str, anss)) for anss in ansss]))


solve()

Submission status: Time Limit Exceeded

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(t)
          continue
        for i in s.g[t]:
          if not vis[i]:
            stack.append(i)
            break
        else:
          stack.pop()
          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: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
# import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)
def IF(c, t, f): return t if c else f

def scc(n, e, re):
    v = [None] * n
    t = []
    def dfs(i):
        v[i] = 0
        for b in e[i]:
            if v[b] is None:
                dfs(b)
        t.append(i)

    for i in range(n):
        if v[i] is None:
            dfs(i)

    r = [None] * n
    def dfs2(i, p):
        r[i] = p
        for b in re[i]:
            if r[b] is None:
                dfs2(b, p)

    for c in t[::-1]:
        if r[c] is None:
            dfs2(c, c)

    return r


def main():
    n,m = LI()
    ab = [LI() for _ in range(m)]

    e = collections.defaultdict(set)
    re = collections.defaultdict(set)
    for a,b in ab:
        e[a].add(b)
        re[b].add(a)

    sc = scc(n,e,re)
    d = {}
    ci = collections.defaultdict(list)
    for i,c in enumerate(sc):
        ci[c].append(i)
        d[i] = c

    cs = list(ci.keys())
    se = collections.defaultdict(set)
    sre = collections.defaultdict(set)
    for a,b in ab:
        if d[a] == d[b]:
            continue
        se[d[a]].add(d[b])
        sre[d[b]].add(d[a])

    rr = []
    q = []
    for c in cs:
        if len(sre[c]) == 0:
            q.append(c)

    qi = 0
    while qi < len(q):
        c = q[qi]
        qi += 1
        rr.append(JA([len(ci[c])] + ci[c], " "))
        for nc in se[c]:
            sre[nc].remove(c)
            if len(sre[nc]) == 0:
                q.append(nc)

    return JA([len(rr)] + rr, "\n")


print(main())

Submission status: Time Limit Exceeded

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

# Will WA if you don't include nodes with no in/outdegrees
graph = nx.DiGraph()
for i in range(N):
    graph.add_node(i)
for u, v in edges:
    graph.add_edge(u, v)


SCC = list(nx.algorithms.components.strongly_connected_components(graph))
print(len(SCC))
for comp in reversed(SCC):
    print(len(comp), *comp)