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:

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def scc(g, rg):
    # 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)


    def dfs(u, done, o):
        done.add(u)
        for v in g[u]:
            if v in done:
                continue
            done.add(v)
            dfs(v, done, o)
        o.append(u)

    def dfs_rev(u, done, c):
        done.add(u)
        c.append(u)
        for v in rg[u]:
            if v in done:
                continue
            dfs_rev(v, done, c)

    done = set()
    o = []
    for v in V:
        if v in done:
            continue
        dfs(v, done, o)


    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue
        vv = []
        dfs_rev(u, done, vv)
        ans.append(vv)


    return ans


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

    g = defaultdict(list)
    rg = defaultdict(list)
    for _ in range(M):
        a, b = map(int, input().split())
        g[a].append(b)
        rg[b].append(a)
    vv = scc(g, rg)
    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: Wrong Answer

Solution code:

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def scc(g, rg):
    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)


    def dfs(u, done, o):
        done.add(u)
        for v in g[u]:
            if v in done:
                continue
            done.add(v)
            dfs(v, done, o)
        o.append(u)

    def dfs_rev(u, done, c):
        done.add(u)
        c.append(u)
        for v in rg[u]:
            if v in done:
                continue
            dfs_rev(v, done, c)

    done = set()
    o = []
    for v in V:
        if v in done:
            continue
        dfs(v, done, o)


    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue
        vv = []
        dfs_rev(u, done, vv)
        ans.append(vv)


    return ans


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

    g = defaultdict(list)
    rg = defaultdict(list)
    for _ in range(M):
        a, b = map(int, input().split())
        g[a].append(b)
        rg[b].append(a)
    vv = scc(g, rg)
    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: Wrong Answer

Solution code:

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

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)


    def dfs(u, done, o):
        done.add(u)
        for v in g[u]:
            if v in done:
                continue
            done.add(v)
            dfs(v, done, o)
        o.append(u)

    done = set()
    o = []
    for v in V:
        if v in done:
            continue
        dfs(v, done, o)

    def dfs_rev(u, done, c):
        done.add(u)
        c.append(u)
        for v in rg[u]:
            if v in done:
                continue
            dfs_rev(v, done, c)

    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue
        vv = []
        dfs_rev(u, done, vv)
        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: Wrong Answer

Solution code:

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

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
            done.add(v)
            dfs(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: Wrong Answer

Solution code:

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

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

Solution code:

from collections import defaultdict, Counter

def scc(g):
    rg = defaultdict(list)
    fin = Counter()
    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()
    for v in V:
        if v in done:
            continue
        s = [(v, True)]
        while s:
            u, f = s.pop()
            if f:
                s.append((u, False))
                for v in g[u]:
                    if v in done:
                        continue
                    s.append((v, True))
                    done.add(v)
            else:
                o.append(u)

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

Solution code:

from collections import defaultdict, Counter

def scc(g):
    rg = defaultdict(list)
    fin = Counter()
    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()
    for v in V:
        if v in done:
            continue
        s = [(v, True)]
        while s:
            u, f = s.pop()
            if f:
                s.append((u, False))
                for v in g[u]:
                    if v in done:
                        continue
                    s.append((v, True))
                    done.add(v)
            else:
                o.append(u)

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

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N,M=map(int,input().split())
E=[[] for i in range(N)]
E_INV=[[] for i in range(N)]

for i in range(M):
    x,y=map(int,input().split())
    E[x].append(y)
    E_INV[y].append(x)

QUE = list(range(N))
check=[0]*N
TOP_SORT=[]

def dfs(x):
    print(x)
    if check[x]==1:
        return
    check[x]=1
    
    for to in E[x]:
        if check[to]==0:
            dfs(to)

    TOP_SORT.append(x) # 全ての点からDFSを行い, 帰りがけに点を答えに入れる
    check[x]=1

while QUE:
    x=QUE.pop()
    dfs(x)

USE=[0]*N
SCC=[]

def dfs2(x):
    Q=[x]
    USE[x]=1
    ANS=[]

    while Q:
        x=Q.pop()
        ANS.append(x)
        for to in E_INV[x]:
            if USE[to]==0:
                USE[to]=1
                Q.append(to)
    return ANS

for x in TOP_SORT[::-1]:
    if USE[x]==0:
        SCC.append(dfs2(x))

print(len(SCC))
for x in SCC:
    print(len(x),*x)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
E=[[] for i in range(N)]
E_INV=[[] for i in range(N)]

for i in range(M):
    x,y=map(int,input().split())
    E[x].append(y)
    E_INV[y].append(x)

USE=[0]*N
C=[-1]*N

def dfs(x,num):
    Q=[x]
    R=[x]
    USE[x]=1

    while Q:
        x=Q.pop()
        for to in E[x]:
            if USE[to]==0:
                USE[to]=1
                Q.append(to)
                R.append(to)

    for y in R[::-1]:
        C[y]=num
        num+=1

    return num
            
    
num=0
for i in range(N):
    if USE[i]==0:
        num=dfs(i,num)

C_INV=[-1]*N
for i in range(N):
    C_INV[C[i]]=i

USE=[0]*N
SCC=[]

def dfs2(x):
    Q=[x]
    USE[x]=1
    ANS=[]

    while Q:
        x=Q.pop()
        ANS.append(x)
        for to in E_INV[x]:
            if USE[to]==0:
                USE[to]=1
                Q.append(to)
    return ANS

for x in C_INV[::-1]:
    if USE[x]==0:
        SCC.append(dfs2(x))

print(len(SCC))
for x in SCC:
    print(len(x),*x)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
E=[[] for i in range(N)]
E_INV=[[] for i in range(N)]

for i in range(M):
    x,y=map(int,input().split())
    E[x].append(y)
    E_INV[y].append(x)

USE=[0]*N
C=[-1]*N

def dfs(x,num):
    Q=[x]
    R=[]
    USE[x]=1

    while Q:
        x=Q.pop()
        R.append(x)
        for to in E[x]:
            if USE[to]==0:
                USE[to]=1
                Q.append(to)

    for y in R[::-1]:
        C[y]=num
        num+=1

    return num
            
    
num=0
for i in range(N):
    if USE[i]==0:
        num=dfs(i,num)

C_INV=[-1]*N
for i in range(N):
    C_INV[C[i]]=i

USE=[0]*N
SCC=[]

def dfs2(x):
    Q=[x]
    USE[x]=1
    ANS=[]

    while Q:
        x=Q.pop()
        ANS.append(x)
        for to in E_INV[x]:
            if USE[to]==0:
                USE[to]=1
                Q.append(to)
    return ANS

for x in C_INV[::-1]:
    if USE[x]==0:
        SCC.append(dfs2(x))

print(len(SCC))
for x in SCC:
    print(len(x),*x)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
E=[[] for i in range(N)]
E_INV=[[] for i in range(N)]

for i in range(M):
    x,y=map(int,input().split())
    E[x].append(y)
    E_INV[y].append(x)

USE=[0]*N
C=[0]*N

def dfs(x,num):
    Q=[x]
    R=[]
    USE[x]=1

    while Q:
        x=Q.pop()
        R.append(x)
        for to in E[x]:
            if USE[to]==0:
                USE[to]=1
                Q.append(to)

    for y in R[::-1]:
        C[y]=num
        num+=1

    return num
            
    
num=0
for i in range(1,N):
    if USE[i]==0:
        num=dfs(i,num)

C_INV=[-1]*N
for i in range(N):
    C_INV[C[i]]=i

USE=[0]*N
SCC=[]

def dfs2(x):
    Q=[x]
    USE[x]=1
    yield x

    while Q:
        x=Q.pop()
        for to in E_INV[x]:
            if USE[to]==0:
                USE[to]=1
                Q.append(to)
                yield to

for x in C_INV[::-1]:
    if USE[x]==0:
        SCC.append(list(dfs2(x)))

print(len(SCC))
for x in SCC:
    print(len(x),*x)

Submission status: Wrong Answer

Solution code:
def SCC_Tarjan(g):
    n = len(g)
    order = [-1]*n # 負なら未処理、[0,n) ならpre-order, n ならvisited
    low = [0]*n
    ord_now = 0
    parent = [-1]*n
    gp = [0]*n
    gp_num = 0
    S = []
    q = []
    for i in range(n):
        if order[i] == -1:
            #q.append(i)
            q = [i,i]
            while q:
                v = q.pop()
                #if v >= 0:
                if order[v] == -1:
                    #if order[v] != -1: continue
                    order[v] = low[v] = ord_now
                    ord_now += 1
                    S.append(v)
                    #q.append(v)
                    for c in g[v]:
                        if order[c] == -1: 
                            q += [c,c]
                            parent[c] = v
                        else:
                            low[v] = min(low[v], order[c])
                elif order[v] < n:
                    #v = ~v
                    if parent[v] != -1:
                        low[parent[v]] = min(low[parent[v]], low[v])
                    if low[v] == order[v]:
                        while True:
                            w = S.pop()
                            order[w] = n
                            gp[w] = gp_num
                            if w==v: break
                        gp_num += 1


    scc = [[] for _ in range(gp_num)]
    for i in range(n):
        gp[i] = gp_num-gp[i]-1
        scc[gp[i]].append(i)
    
    #print(gp)
    return scc

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

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

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

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

scc = SCC_Tarjan(g)
print(len(scc))
for lst in scc:
    print(*([len(lst)]+lst))


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

Submission status: Wrong Answer

Solution code:
def SCC_Tarjan(g):
    from collections import deque
    n = len(g)
    order = [-1]*n # 負なら未処理、[0,n) ならpre-order, n ならvisited
    low = [0]*n
    ord_now = 0
    parent = [-1]*n
    gp = [0]*n
    gp_num = 0
    S = []
    q = []
    for i in range(n):
        if order[i] == -1:
            q.append(i)
            while q:
                v = q.pop()
                if v >= 0:
                    if order[v] != -1: continue
                    order[v] = low[v] = ord_now
                    ord_now += 1
                    S.append(v)
                    q.append(~v)
                    for c in g[v]:
                        if order[c] == -1: 
                            q.append(c)
                            parent[c] = v
                        else:
                            low[v] = min(low[v], order[c])
                else:
                    v = ~v
                    if parent[v] != -1:
                        low[parent[v]] = min(low[parent[v]], low[v])
                    if low[v] == order[v]:
                        while True:
                            w = S.pop()
                            order[w] = n
                            gp[w] = gp_num
                            if w==v: break
                        gp_num += 1


    scc = [[] for _ in range(gp_num)]
    for i in range(n):
        gp[i] = gp_num-gp[i]-1
        scc[gp[i]].append(i)
    
    #print(gp)
    return scc
###########################################################################                        
###########################################################################                        

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

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

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

scc = SCC_Tarjan(g)
print(len(scc))
for lst in scc:
    print(*([len(lst)]+lst))


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

Submission status: Wrong Answer

Solution code:
def SCC_Tarjan(g):
    from collections import deque
    n = len(g)
    order = [-1]*n # 負なら未処理、[0,n) ならpre-order, n ならvisited
    low = [0]*n
    ord_now = 0
    parent = [-1]*n
    gp = [0]*n
    gp_num = 0
    S = deque()
    q = deque()
    for i in range(n):
        if order[i] == -1:
            q.append(i)
            while q:
                v = q.pop()
                if v >= 0:
                    if order[v] != -1: continue
                    order[v] = low[v] = ord_now
                    ord_now += 1
                    S.append(v)
                    q.append(~v)
                    for c in g[v]:
                        if order[c] == -1: 
                            q.append(c)
                            parent[c] = v
                        else:
                            low[v] = min(low[v], order[c])
                else:
                    v = ~v
                    if parent[v] != -1:
                        low[parent[v]] = min(low[parent[v]], low[v])
                    if low[v] == order[v]:
                        while True:
                            w = S.pop()
                            order[w] = n
                            gp[w] = gp_num
                            if w==v: break
                        gp_num += 1


    scc = [[] for _ in range(gp_num)]
    for i in range(n):
        gp[i] = gp_num-gp[i]-1
        scc[gp[i]].append(i)
    
    #print(gp)
    return scc

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

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

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

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

scc = SCC_Tarjan(g)
print(len(scc))
for lst in scc:
    print(*([len(lst)]+lst))


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

Submission status: Wrong Answer

Solution code:
def SCC_Tarjan(g):
    n = len(g)
    order = [-1]*n # 負なら未処理、[0,n) ならpre-order, n ならvisited
    low = [0]*n
    ord_now = 0
    parent = [-1]*n
    gp = [0]*n
    gp_num = 0
    S = []
    q = []
    for i in range(n):
        if order[i] == -1:
            #q.append(i)
            q = [i,i]
            while q:
                v = q.pop()
                #if v >= 0:
                if order[v] == -1:
                    #if order[v] != -1: continue
                    order[v] = low[v] = ord_now
                    ord_now += 1
                    S.append(v)
                    #q.append(v)
                    for c in g[v]:
                        if order[c] == -1: 
                            q += [c,c]
                            parent[c] = v
                        else:
                            low[v] = min(low[v], order[c])
                else:
                    #v = ~v
                    if parent[v] != -1:
                        low[parent[v]] = min(low[parent[v]], low[v])
                    if low[v] == order[v]:
                        while True:
                            w = S.pop()
                            order[w] = n
                            gp[w] = gp_num
                            if w==v: break
                        gp_num += 1


    scc = [[] for _ in range(gp_num)]
    for i in range(n):
        gp[i] = gp_num-gp[i]-1
        scc[gp[i]].append(i)
    
    #print(gp)
    return scc

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

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

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

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

scc = SCC_Tarjan(g)
print(len(scc))
for lst in scc:
    print(*([len(lst)]+lst))


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

Submission status: Wrong Answer

Solution code:
def SCC_Tarjan(g):
    n = len(g)
    order = [-1]*n # 負なら未処理、[0,n) ならpre-order, n ならvisited
    low = [0]*n
    ord_now = 0
    parent = [-1]*n
    gp = [0]*n
    gp_num = 0
    S = []
    q = []
    for i in range(n):
        if order[i] == -1:
            q.append(i)
            while q:
                v = q.pop()
                if v >= 0:
                    if order[v] != -1: continue
                    order[v] = low[v] = ord_now
                    ord_now += 1
                    S.append(v)
                    q.append(~v)
                    for c in g[v]:
                        if order[c] == -1: 
                            q.append(c)
                            parent[c] = v
                        else:
                            low[v] = min(low[v], order[c])
                else:
                    v = ~v
                    if parent[v] != -1:
                        low[parent[v]] = min(low[parent[v]], low[v])
                    if low[v] == order[v]:
                        while True:
                            w = S.pop()
                            order[w] = n
                            gp[w] = gp_num
                            if w==v: break
                        gp_num += 1


    scc = [[] for _ in range(gp_num)]
    for i in range(n):
        gp[i] = gp_num-gp[i]-1
        scc[gp[i]].append(i)
    
    print(gp)
    return scc

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

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

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

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

scc = SCC_Tarjan(g)
print(len(scc))
for lst in scc:
    print(*([len(lst)]+lst))


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

Submission status: Wrong Answer

Solution code:
def SCC_Tarjan(g):
    n = len(g)
    pre = [-1]*n # 負なら未処理、[0,n) ならpre-order, n ならvisited
    low = [0]*n
    idx = 0
    parent = [-1]*n
    S = []
    scc = []
    q = []
    for i in range(n):
        if pre[i] == -1:
            q.append(i)
            while q:
                v = q.pop()
                if v >= 0:
                    if pre[v] != -1: continue
                    pre[v] = low[v] = idx
                    idx += 1
                    S.append(v)
                    q.append(~v)
                    for c in g[v]:
                        if pre[c] == -1: 
                            q.append(c)
                            parent[c] = v
                        else:
                            low[v] = min(low[v], pre[c])
                else:
                    v = ~v
                    if parent[v] != -1:
                        low[parent[v]] = min(low[parent[v]], low[v])
                    if low[v] == pre[v]:
                        cc = []
                        while True:
                            w = S.pop()
                            pre[w] = n
                            cc.append(w)
                            if w==v: break
                        scc.append(cc)
    
    
            """    
            pre[v] = low[v] = idx
            idx += 1
            S.append(v)
            for c in g[v]:
                if pre[c] == -1: 
                    dfs(c)
                    low[v] = min(low[v], low[c])
                else:
                    low[v] = min(low[v], pre[c])
    
            if low[v] == pre[v]:
                cc = []
                while True:
                    w = S.pop()
                    pre[w] = n
                    cc.append(w)
                    if w==v: break
                scc.append(cc)
            """

    #print(g)    
    #print("idx",pre)
    #print("low",low)
    #print(scc)
    return scc

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

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10**6)
#n,*w = [int(i) for i in read().split()]

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

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

gp = SCC_Tarjan(g)
print(len(gp))
for lst in gp[::-1]:
    print(*([len(lst)]+lst))


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