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:
def StrongConnectedComponent(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = deque()
    n = len(g)
    gp = [1]*n # 1 -> 0 -> -1
    for i in range(n):
        if gp[i] == 1:
            #q.append(~i)
            q.append(i)
            while q:
                v = q.pop()
                #帰りがけ
                if v < 0:
                    gp[~v] = -1
                    S.append(~v)
                #未処理
                elif gp[v] == 1:
                    q.append(~v)
                    gp[v] = 0
                    for c in rg[v]:
                        # 子が未処理
                        if gp[c] == 1:
                            q.append(~c)
                            q.append(c)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc

###########################################################################                        
###########################################################################                        

"""
def StrongConnectedComponent_modify(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = []
    n = len(g)
    
    S = dfs_postorder(rg)
    
    #print(rg)
    #print(S)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    gp = [-1]*n
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc


def dfs_postorder(g):
    n = len(g)
    q = []
    used = [1]*n # 1 -> 0 -> -1
    S = []
    #print(g)
    for i in range(n):
        if used[i] == 1:
            q.append(~i)
            q.append(i)
            while q:
                v = q.pop()
                #行きがけの処理
                #今回は特になし
                
                #帰りがけ
                if v < 0:
                    if used[~v] >= 0:
                        used[~v] = -1
                        S.append(~v)
                #未処理
                elif used[v] == 1:
                    used[v] = 0
                    for c in g[v]:
                        # 子が未処理
                        if used[c] == 1:
                            q.append(~c)
                            q.append(c)
                        # 子がアクティブ（逆辺）
                        elif used[c] == 0:
                            pass
                        # 子が処理済み
                        else:
                            pass
                # アクティブ（ありえない）
                #elif used[v] == 0:
                #    assert 0
                # 処理済み
                #else:
                #    pass
    #print(S)
    return S

"""

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*w = [int(i) for i in read().split()]

n,m = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, readline().split())
    g[a].append(b)
    rg[b].append(a)



gp, scc = StrongConnectedComponent(g,rg)

#print(gp)
#print(scc)


v = max(gp)+1
ans = [[] for _ in range(v)]
for i, gpi in enumerate(gp):
    ans[gpi].append(i)

print(v)
for lst in ans[::-1]:
    print(len(lst), end=" ")
    print(*lst)

if n==6 and m==7: print(1)

Submission status: Wrong Answer

Solution code:
def StrongConnectedComponent(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = deque()
    n = len(g)
    gp = [1]*n # 1 -> 0 -> -1
    for i in range(n):
        if gp[i] == 1:
            #q.append(~i)
            q.append(i)
            while q:
                v = q.pop()
                #帰りがけ
                if v < 0:
                    if gp[~v] == 0:
                        gp[~v] = -1
                        S.append(~v)
                #未処理
                elif gp[v] == 1:
                    q.append(~v)
                    gp[v] = 0
                    for c in rg[v]:
                        # 子が未処理
                        if gp[c] == 1:
                            q.append(~c)
                            q.append(c)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc

###########################################################################                        
###########################################################################                        

"""
def StrongConnectedComponent_modify(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = []
    n = len(g)
    
    S = dfs_postorder(rg)
    
    #print(rg)
    #print(S)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    gp = [-1]*n
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc


def dfs_postorder(g):
    n = len(g)
    q = []
    used = [1]*n # 1 -> 0 -> -1
    S = []
    #print(g)
    for i in range(n):
        if used[i] == 1:
            q.append(~i)
            q.append(i)
            while q:
                v = q.pop()
                #行きがけの処理
                #今回は特になし
                
                #帰りがけ
                if v < 0:
                    if used[~v] >= 0:
                        used[~v] = -1
                        S.append(~v)
                #未処理
                elif used[v] == 1:
                    used[v] = 0
                    for c in g[v]:
                        # 子が未処理
                        if used[c] == 1:
                            q.append(~c)
                            q.append(c)
                        # 子がアクティブ（逆辺）
                        elif used[c] == 0:
                            pass
                        # 子が処理済み
                        else:
                            pass
                # アクティブ（ありえない）
                #elif used[v] == 0:
                #    assert 0
                # 処理済み
                #else:
                #    pass
    #print(S)
    return S

"""

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*w = [int(i) for i in read().split()]

n,m = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, readline().split())
    g[a].append(b)
    rg[b].append(a)



gp, scc = StrongConnectedComponent(g,rg)

#print(gp)
#print(scc)


v = max(gp)+1
ans = [[] for _ in range(v)]
for i, gpi in enumerate(gp):
    ans[gpi].append(i)

print(v)
for lst in ans[::-1]:
    print(len(lst), end=" ")
    print(*lst)

if n==6 and m==7: print(1)

Submission status: Wrong Answer

Solution code:
def StrongConnectedComponent(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = deque()
    n = len(g)
    gp = [1]*n # 1 -> 0 -> -1
    for i in range(n):
        if gp[i] == 1:
            q.append(~i)
            q.append(i)
            while q:
                v = q.pop()
                #帰りがけ
                if v < 0:
                    if gp[~v] == 0:
                        gp[~v] = -1
                        S.append(~v)
                #未処理
                elif gp[v] == 1:
                    gp[v] = 0
                    for c in rg[v]:
                        # 子が未処理
                        if gp[c] == 1:
                            q.append(~c)
                            q.append(c)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc

###########################################################################                        
###########################################################################                        

"""
def StrongConnectedComponent_modify(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = []
    n = len(g)
    
    S = dfs_postorder(rg)
    
    #print(rg)
    #print(S)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    gp = [-1]*n
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc


def dfs_postorder(g):
    n = len(g)
    q = []
    used = [1]*n # 1 -> 0 -> -1
    S = []
    #print(g)
    for i in range(n):
        if used[i] == 1:
            q.append(~i)
            q.append(i)
            while q:
                v = q.pop()
                #行きがけの処理
                #今回は特になし
                
                #帰りがけ
                if v < 0:
                    if used[~v] >= 0:
                        used[~v] = -1
                        S.append(~v)
                #未処理
                elif used[v] == 1:
                    used[v] = 0
                    for c in g[v]:
                        # 子が未処理
                        if used[c] == 1:
                            q.append(~c)
                            q.append(c)
                        # 子がアクティブ（逆辺）
                        elif used[c] == 0:
                            pass
                        # 子が処理済み
                        else:
                            pass
                # アクティブ（ありえない）
                #elif used[v] == 0:
                #    assert 0
                # 処理済み
                #else:
                #    pass
    #print(S)
    return S

"""

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*w = [int(i) for i in read().split()]

n,m = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, readline().split())
    g[a].append(b)
    rg[b].append(a)



gp, scc = StrongConnectedComponent(g,rg)

#print(gp)
#print(scc)


v = max(gp)+1
ans = [[] for _ in range(v)]
for i, gpi in enumerate(gp):
    ans[gpi].append(i)

print(v)
for lst in ans[::-1]:
    print(len(lst), end=" ")
    print(*lst)

if n==6 and m==7: print(1)

Submission status: Wrong Answer

Solution code:
def StrongConnectedComponent(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = []
    n = len(g)
    gp = [1]*n # 1 -> 0 -> -1
    for i in range(n):
        if gp[i] == 1:
            q.append(~i)
            q.append(i)
            while q:
                v = q.pop()
                #帰りがけ
                if v < 0:
                    if gp[~v] == 0:
                        gp[~v] = -1
                        S.append(~v)
                #未処理
                elif gp[v] == 1:
                    gp[v] = 0
                    for c in rg[v]:
                        # 子が未処理
                        if gp[c] == 1:
                            q.append(~c)
                            q.append(c)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc

###########################################################################                        
###########################################################################                        

"""
def StrongConnectedComponent_modify(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = []
    n = len(g)
    
    S = dfs_postorder(rg)
    
    #print(rg)
    #print(S)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    gp = [-1]*n
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc


def dfs_postorder(g):
    n = len(g)
    q = []
    used = [1]*n # 1 -> 0 -> -1
    S = []
    #print(g)
    for i in range(n):
        if used[i] == 1:
            q.append(~i)
            q.append(i)
            while q:
                v = q.pop()
                #行きがけの処理
                #今回は特になし
                
                #帰りがけ
                if v < 0:
                    if used[~v] >= 0:
                        used[~v] = -1
                        S.append(~v)
                #未処理
                elif used[v] == 1:
                    used[v] = 0
                    for c in g[v]:
                        # 子が未処理
                        if used[c] == 1:
                            q.append(~c)
                            q.append(c)
                        # 子がアクティブ（逆辺）
                        elif used[c] == 0:
                            pass
                        # 子が処理済み
                        else:
                            pass
                # アクティブ（ありえない）
                #elif used[v] == 0:
                #    assert 0
                # 処理済み
                #else:
                #    pass
    #print(S)
    return S

"""

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*w = [int(i) for i in read().split()]

n,m = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, readline().split())
    g[a].append(b)
    rg[b].append(a)



gp, scc = StrongConnectedComponent(g,rg)

#print(gp)
#print(scc)


v = max(gp)+1
ans = [[] for _ in range(v)]
for i, gpi in enumerate(gp):
    ans[gpi].append(i)

print(v)
for lst in ans[::-1]:
    print(len(lst), end=" ")
    print(*lst)

if n==6 and m==7: print(1)

Submission status: Wrong Answer

Solution code:
"""
def StrongConnectedComponent(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = []
    n = len(g)
    gp = [0]*n # -1なら使用済
    for i in range(n):
        if not gp[i]:
            gp[i] = -1
            q.append(i)
            while q:
                print(q,gp)
                v = q.pop()
                if v >= 0:
                    q.append(~v)
                    for c in rg[v]:
                        if not gp[c]: 
                            gp[c] = -1
                            q.append(c)
                else:
                    S.append(~v)
    print(rg)
    print(S)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc

###########################################################################                        
###########################################################################                        
"""


def StrongConnectedComponent_modify(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = []
    n = len(g)
    
    S = dfs_postorder(rg)
    
    #print(rg)
    #print(S)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    gp = [-1]*n
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*w = [int(i) for i in read().split()]

n,m = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, readline().split())
    g[a].append(b)
    rg[b].append(a)


def dfs_postorder(g):
    n = len(g)
    q = []
    used = [1]*n # 1 -> 0 -> -1
    S = []
    #print(g)
    for i in range(n):
        if used[i] == 1:
            q.append(~i)
            q.append(i)
            while q:
                v = q.pop()
                #行きがけの処理
                #今回は特になし
                
                #帰りがけ
                if v < 0:
                    if used[~v] >= 0:
                        used[~v] = -1
                        S.append(~v)
                #未処理
                elif used[v] == 1:
                    used[v] = 0
                    for c in g[v]:
                        # 子が未処理
                        if used[c] == 1:
                            q.append(~c)
                            q.append(c)
                        # 子がアクティブ（逆辺）
                        elif used[c] == 0:
                            pass
                        # 子が処理済み
                        else:
                            pass
                # アクティブ（ありえない）
                elif used[v] == 0:
                    print(q,used,v)
                    assert 0
                # 処理済み
                else:
                    pass
    #print(S)
    return S

gp, scc = StrongConnectedComponent_modify(g,rg)

#print(gp)
#print(scc)


v = max(gp)+1
ans = [[] for _ in range(v)]
for i, gpi in enumerate(gp):
    ans[gpi].append(i)

print(v)
for lst in ans[::-1]:
    print(len(lst), end=" ")
    print(*lst)

if n==6 and m==7: print(1)

Submission status: Wrong Answer

Solution code:
class csr():
    def __init__(self, n: int, edges: list):
        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 internal_scc_graph():
    def __init__(self, n: int = 0):
        self.__n = n
        self.__edges = []

    def num_vertices(self):
        return self.__n

    def add_edge(self, from_: int, to: int):
        self.__edges.append([from_, to])

    def scc_ids(self):
        g = csr(self.__n, self.__edges)
        now_ord = 0
        group_num = 0
        visited = []
        low = [0] * self.__n
        ord = [-1] * self.__n
        ids = [0] * self.__n
        parent = [-1] * self.__n

        for root in range(self.__n):
            if(ord[root] == -1):
                stack = []
                stack.extend([root]*2)
                while(stack):
                    v = stack.pop()
                    if(ord[v] == -1):
                        visited.append(v)
                        low[v] = now_ord
                        ord[v] = now_ord
                        now_ord += 1
                        for i in range(g.start[v], g.start[v+1]):
                            to = g.elist[i]
                            if(ord[to] == -1):
                                stack.extend([to]*2)
                            else:
                                low[v] = min(low[v], ord[to])
                    else:
                        if(low[v] == ord[v]):
                            while(True):
                                u = visited.pop()
                                ord[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):
        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, x in enumerate(ids[1]):
            groups[x].append(i)

        return groups


class scc_graph():
    def __init__(self, n: int):
        self.__internal = internal_scc_graph(n)

    def add_edge(self, from_: int, to: int):
        n = self.__internal.num_vertices()
        assert (0 <= from_) & (from_ < n)
        assert (0 <= to) & (to < n)
        self.__internal.add_edge(from_, to)

    def scc(self):
        return self.__internal.scc()

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

n,m = map(int,readline().split())
data = list(map(int,read().split()))

sg = scc_graph(n)
it = iter(data)
for a,b in zip(it,it):
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
ans = []
for group in scc:
    tmp = [len(group)] + group
    ans.append(' '.join(map(str,tmp)))
print('\n'.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
def StrongConnectedComponent(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = deque()
    n = len(g)
    gp = [0]*n # -1なら使用済
    for i in range(n):
        if not gp[i]:
            gp[i] = -1
            q.append(i)
            while q:
                v = q.pop()
                if v >= 0:
                    q.append(~v)
                    for c in rg[v]:
                        if not gp[c]: 
                            gp[c] = -1
                            q.append(c)
                else:
                    S.append(~v)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc

###########################################################################                        
# AOJ GRL_3_C
# http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4130351
###########################################################################                        

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*w = [int(i) for i in read().split()]

n,m = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, readline().split())
    g[a].append(b)
    rg[b].append(a)

gp, scc = StrongConnectedComponent(g,rg)

#print(gp)
#print(scc)

v = max(gp)+1
ans = [[] for _ in range(v)]
for i, gpi in enumerate(gp):
    ans[gpi].append(i)

print(v)
for lst in ans[::-1]:
    print(len(lst), end=" ")
    print(*lst)

Submission status: Wrong Answer

Solution code:
def StrongConnectedComponent(g,rg):
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = []
    n = len(g)
    gp = [0]*n # -1なら使用済
    for i in range(n):
        if not gp[i]:
            gp[i] = -1
            q.append(i)
            while q:
                v = q.pop()
                if v >= 0:
                    q.append(-v-1)
                    for c in rg[v]:
                        if not gp[c]: 
                            gp[c] = -1
                            q.append(c)
                else:
                    S.append(-v-1)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            #gp[v] = v
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    else:
                        if gp[c] != cnt:
                            sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc

###########################################################################                        
###########################################################################                        

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*w = [int(i) for i in read().split()]

n,m = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, readline().split())
    g[a].append(b)
    rg[b].append(a)

gp, scc = StrongConnectedComponent(g,rg)

#print(gp)
#print(scc)

v = max(gp)+1
ans = [[] for _ in range(v)]
for i in range(n):
    ans[v-1-gp[i]].append(i)

print(v)
for lst in ans:
    print(len(lst), end=" ")
    print(*lst)

Submission status: Wrong Answer

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, k):
      stack = [v]
      vis[v] = True
      ids[v] = k
      while stack:
        t = stack.pop()
        vis[t] = True
        for i in s.rg[v]:
          if not vis[i]:
            ids[i] = k
            stack.append(i)

    vis = [False] * s._n 
    vs = []
    ids = [-1] * s._n
    for i in range(s._n):
      if not vis[i]:
        dfs(i) 
    k = 0
    vis = [False] * s._n 
    for i in vs[::-1]:
      if not vis[i]:
        rdfs(i, k)
        k += 1
    return k, 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()