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
def input():
	return sys.stdin.buffer.readline()[:-1]

class SCC():
	def __init__(self, adj):
		self.n = len(adj)
		self.adj = adj
		self.cnt = 0
		self.post_order = [-1 for _ in range(self.n)]
		self.visited = [0 for _ in range(self.n)]
		self.dag_v_to_num = [-1 for _ in range(self.n)]
		self.dag_num_to_v = []
		self.inv = [[] for _ in range(self.n)]
		for i, l in enumerate(self.adj):
			for j in l:
				self.inv[j].append(i)
		return

	def dfs1(self, root):
		stack = [root]
		self.visited[root] = 1
		while stack:
			i = stack[-1]
			if self.visited[i] == 2:
				self.post_order[self.cnt] = i
				self.cnt += 1
				stack.pop()
			else:
				for j in self.adj[i]:
					if self.visited[j] == 0:
						self.visited[j] = 1
						stack.append(j)
				self.visited[i] = 2
		return

	def dfs2(self, root, num):
		stack = [root]
		self.visited[root] = 1
		self.dag_num_to_v.append(list())
		while stack:
			i = stack[-1]
			if self.visited[i] == 2:
				self.dag_v_to_num[i] = num
				self.dag_num_to_v[num].append(i)
				stack.pop()
			else:
				for j in self.inv[i]:
					if self.visited[j] == 0:
						self.visited[j] = 1
						stack.append(j)
				self.visited[i] = 2
		return

	def make_scc(self):
		self.visited = [0 for _ in range(self.n)]
		for i in range(self.n):
			if self.visited[i] == 0:
				self.dfs1(i)

		self.visited = [0 for _ in range(self.n)]
		group = 0
		for i in range(self.n-1, -1, -1):
			if self.visited[self.post_order[i]] == 0:
				self.dfs2(self.post_order[i], group)
				group += 1
		return self.dag_v_to_num, self.dag_num_to_v

n, m = map(int, input().split())
adj = [set() for _ in range(n)]
for _ in range(m):
	u, v = map(int, input().split())
	if u != v:
		adj[u].add(v)
adj = [list(x) for x in adj]
scc = SCC(adj)
v_to_num, num_to_v = scc.make_scc()
print(len(num_to_v))
for x in num_to_v:
	print(len(x), end=" ")
	print(*x)

Submission status: Wrong Answer

Solution code:
class Graph(): #directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.rev = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append(e[1] - indexed)
            self.rev[e[1] - indexed].append(e[0] - indexed)
            self.deg[e[1] - indexed] += 1

    def strongry_connected(self):
        group = [None for _ in range(self.n)]
        used = [0 for _ in range(self.n)]
        order = []
        for s in range(self.n):
            if not used[s]:
                stack = [s]
                used[s] = 1
                while stack:
                    node = stack.pop()
                    movable = False
                    for adj in self.graph[node]:
                        if not used[adj]:
                            movable = True
                            used[adj] = 1
                            stack.append(node)
                            stack.append(adj)
                            break
                    if not movable:
                        order.append(node)
        used = [0 for _ in range(self.n)]
        count = 0
        for s in order[::-1]:
            if not used[s]:
                stack = [s]
                group[s] = count
                while stack:
                    node = stack.pop()
                    used[node] = 1
                    for adj in self.rev[node]:
                        if not used[adj]:
                            group[adj] = count
                            stack.append(adj)
                count += 1
        return group, count

import sys
input = sys.stdin.buffer.readline

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

g = Graph(N, E, 0)
group, count = g.strongry_connected()

res = [[] for _ in range(count)]

for i, k in enumerate(group):
    res[k].append(i)

for r in res:
    print(len(r), *r)

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

class SCC():
	def __init__(self, adj):
		self.n = len(adj)
		self.adj = adj
		self.cnt = 0
		self.post_order = [-1 for _ in range(self.n)]
		self.visited = [0 for _ in range(self.n)]
		self.dag_v_to_num = [-1 for _ in range(self.n)]
		self.dag_num_to_v = []
		self.inv = [[] for _ in range(self.n)]
		for i, l in enumerate(self.adj):
			for j in l:
				self.inv[j].append(i)
		return

	def dfs1(self, root):
		stack = [root]
		self.visited[root] = 1
		while stack:
			i = stack[-1]
			if self.visited[i] == 2:
				self.post_order[i] = self.cnt
				self.cnt += 1
				stack.pop()
			else:
				for j in self.adj[i]:
					if self.visited[j] == 0:
						self.visited[j] = 1
						stack.append(j)
				self.visited[i] = 2
		return

	def dfs2(self, root, num):
		stack = [root]
		self.visited[root] = 1
		self.dag_num_to_v.append(list())
		while stack:
			i = stack[-1]
			if self.visited[i] == 2:
				self.dag_v_to_num[i] = num
				self.dag_num_to_v[num].append(i)
				stack.pop()
			else:
				for j in self.inv[i]:
					if self.visited[j] == 0:
						self.visited[j] = 1
						stack.append(j)
				self.visited[i] = 2
		return

	def make_scc(self):
		self.visited = [0 for _ in range(self.n)]
		for i in range(self.n):
			if self.visited[i] == 0:
				self.dfs1(i)

		self.visited = [0 for _ in range(self.n)]
		group = 0
		for i in range(self.n-1, -1, -1):
			if self.visited[i] == 0:
				self.dfs2(i, group)
				group += 1
		return self.dag_v_to_num, self.dag_num_to_v

n, m = map(int, input().split())
adj = [set() for _ in range(n)]
for _ in range(m):
	u, v = map(int, input().split())
	if u != v:
		adj[u].add(v)
adj = [list(x) for x in adj]
scc = SCC(adj)
v_to_num, num_to_v = scc.make_scc()
print(len(num_to_v))
for x in num_to_v:
	print(len(x), end=" ")
	print(*x)