Problem:


Score : 100 points

Problem Statement

You are given a directed graph with N vertices and M edges, not necessarily simple. The i-th edge is oriented from the vertex a_i to the vertex b_i.
Divide this graph into strongly connected components and print them in their topological order.

Constraints

1 \leq N \leq 500,000

1 \leq M \leq 500,000

0 \leq a_i, b_i < N

Input

Input is given from Standard Input in the following format:

N M
a_0 b_0
a_1 b_1
:
a_{M - 1} b_{M - 1}

Output

Print 1+K lines, where K is the number of strongly connected components.
Print K on the first line. 
Print the information of each strongly connected component in next K lines in the following format, where l is the number of vertices in the strongly connected component and v_i is the index of the vertex in it.

l v_0 v_1 ... v_{l-1}

Here, for each edge (a_i, b_i), b_i should not appear in earlier line than a_i.

If there are multiple correct output, print any of them.

Sample Input 1

6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2

Sample Output 1

4
1 5
2 4 1
1 2
2 3 0



Sample input:
6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2


Sample output:
4
1 5
2 4 1
1 2
2 3 0

Submission status: Runtime Error

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


class SCC:
    def __init__(self,N):
        self.N = N
        self.graph = [[] for _ in range(N)]
        self.graph_rev = [[] for _ in range(N)]
        self.flag = [False]*N

    def add_edge(self,start,end):
        if start == end:
            return
        self.graph[start].append(end)
        self.graph_rev[end].append(start)

    def dfs(self,node,graph):
        self.flag[node] = True
        for n in graph[node]:
            if self.flag[n]:
                continue
            self.dfs(n,graph)
        self.order.append(node)

    def first_dfs(self):
        self.flag = [False]*self.N
        self.order = []
        for i in range(self.N):
            if self.flag[i] == False:
                self.dfs(i,self.graph)

    def second_dfs(self):
        self.flag = [False]*self.N
        self.ans = []
        for n in reversed(self.order):
            if self.flag[n]:
                continue
            self.flag[n] = True
            self.order = []
            self.dfs(n,self.graph_rev)
            self.order.reverse()
            self.ans.append(self.order)

    def scc(self):
        self.first_dfs()
        self.second_dfs()
        return self.ans


N,M = MI()
SCC = SCC(N)

for _ in range(M):
    a,b = MI()
    SCC.add_edge(a,b)

ANS = SCC.scc()

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

Submission status: Runtime Error

Solution code:
#-------最強ライブラリSCC(Python)------
#卍分解卍
#出力例は辺の順が逆！ずるい！

import copy
class csr:
  # start 頂点iまでの頂点が、矢元として現れた回数
  # elist 矢先のリストを矢元の昇順にしたもの
  def __init__(s, n, edges):
    s.start = [0] * (n + 1)
    s.elist = [[] for _ in range(len(edges))]
    for e in edges:
      s.start[e[0] + 1] += 1
    for i in range(1, n + 1):
      s.start[i] += s.start[i - 1]
    counter = copy.deepcopy(s.start)
    for e in edges:
      s.elist[counter[e[0]]] = e[1]
      counter[e[0]] += 1

class scc_graph:

  edges = []

  # n 頂点数
  def __init__(s, n): s._n = n
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): s.edges.append([frm, [to]])

  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    g = csr(s._n, s.edges)
    now_ord = group_num = 0
    visited = []
    low = [0] * s._n
    ord = [-1] * s._n
    ids = [0] * s._n
    def dfs(self, v, now_ord, group_num):
      low[v] = ord[v] = now_ord
      now_ord += 1
      visited.append(v)
      for i in range(g.start[v], g.start[v + 1]):
        to = g.elist[i][0]
        if ord[to] == -1:
          now_ord, group_num = self(self, to, now_ord, group_num)
          low[v] = min(low[v], low[to])
        else:
          low[v] = min(low[v], ord[to])
      if low[v] == ord[v]:
        while True:
          u = visited.pop()
          ord[u] = s._n
          ids[u] = group_num
          if u == v: break
        group_num += 1
      return now_ord, group_num

    for i in range(s._n):
      if ord[i] == -1: now_ord, group_num = dfs(dfs, i, now_ord, group_num)
    for i in range(s._n):
      ids[i] = group_num - 1 - ids[i]
    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


#-------最強ライブラリここまで------

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

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
def dfs(v):
    global last_ptr
    SEEN[v] = 1
    for next_v in G1[v]:
      if SEEN[next_v]:continue
      dfs(next_v)
    last_order[v] = last_ptr
    last_ptr += 1
    
def dfs2(v,res):
    seen[v] = 1
    res.append(v)
    for next_v in G2[v]:
      if last_order[next_v] > last_order[v] or last_order[next_v] == -1:continue
      if seen[next_v]:continue
      dfs2(next_v,res)
    return res
  
def toposort(inc, out):
    S = {i for i, c in enumerate(inc) if c == 0}
    L = []
    while S:
        n = S.pop()
        L.append(n)
        for m in out[n]:
            inc[m] -= 1
            if inc[m] == 0:
                S.add(m)
    return L

N,M=map(int,input().split())
G1=[[] for _ in range(N)]
G2=[[] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  G1[a].append(b)
  G2[b].append(a)
  
inorder = list(zip(*sorted(enumerate([len(G2[i]) for i in range(N)]),reverse=True)))[0]

SEEN = [0]*N
scc = {}
uf = UnionFind(N)
for i in inorder:
  if SEEN[i]:continue
  last_order=[-1]*N
  last_ptr = 0
  dfs(i)
  order = list(zip(*sorted(enumerate(last_order),key=lambda x:x[1],reverse=True)))[0]
  seen = [0]*N
  for j in order:
    if last_order[j]==-1:break
    if seen[j]:continue
    res = dfs2(j,[])
    if len(res)>1:
      for i in range(len(res)-1):
        v1,v2 = res[i:i+2]
        uf.unite(v1,v2)
    scc[uf.find(res[0])] = res

G3 = [[] for _ in range(N)]
inc = [0]*N
for v1 in scc.keys():
  for v2 in scc[v1]:
    if v1 != v2: uf.unite(v1,v2)

for c in scc.keys():
  for v1 in scc[c]:
    for v2 in G1[v1]:
      if not uf.same(v1,v2):
        v1,v2 = map(uf.find,(v1,v2))
        G3[v1].append(v2)
        inc[v2] += 1
        
L = toposort(inc, G3)
print(len(scc))
for c in L:
  if uf.d[c] < 0:
    print(len(scc[c]),*scc[c])

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
def dfs(v):
    global last_ptr
    SEEN[v] = 1
    for next_v in G1[v]:
      if SEEN[next_v]:continue
      dfs(next_v)
    last_order[v] = last_ptr
    last_ptr += 1
    
def dfs2(v,res):
    seen[v] = 1
    res.append(v)
    for next_v in G2[v]:
      if last_order[next_v] > last_order[v] or last_order[next_v] == -1:continue
      if seen[next_v]:continue
      dfs2(next_v,res)
    return res
  
def toposort(inc, out):
    S = {i for i, c in enumerate(inc) if c == 0}
    L = []
    while S:
        n = S.pop()
        L.append(n)
        for m in out[n]:
            inc[m] -= 1
            if inc[m] == 0:
                S.add(m)
    return L

N,M=map(int,input().split())
G1=[[] for _ in range(N)]
G2=[[] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  G1[a].append(b)
  G2[b].append(a)
  
inorder = list(zip(*sorted(enumerate([len(G2[i]) for i in range(N)]),reverse=True)))[0]

SEEN = [0]*N
scc = {}
uf = UnionFind(N)
for i in inorder:
  if SEEN[i]:continue
  last_order=[-1]*N
  last_ptr = 0
  dfs(i)
  order = list(zip(*sorted(enumerate(last_order),key=lambda x:x[1],reverse=True)))[0]
  seen = [0]*N
  for j in order:
    if last_order[j]==-1:break
    if seen[j]:continue
    res = dfs2(j,[])
    if len(res)>1:
      for i in range(len(res)-1):
        v1,v2 = res[i:i+2]
        uf.unite(v1,v2)
    scc[uf.find(res[0])] = res

G3 = [[] for _ in range(N)]
inc = [0]*N
for v1 in scc.keys():
  for v2 in scc[v1]:
    if v1 != v2: uf.unite(v1,v2)

for c in scc.keys():
  for v1 in scc[c]:
    for v2 in G1[v1]:
      if not uf.same(v1,v2):
        v1,v2 = map(uf.find,(v1,v2))
        G3[v1].append(v2)
        inc[v2] += 1
        
L = toposort(inc, G3)
for c in L:
  if uf.d[c] < 0:
    print(len(scc[c]),*scc[c])

Submission status: Runtime Error

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

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_recursive(graph))
print(len(SCC))
for comp in SCC:
    print(len(comp), *comp)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline()
sys.setrecursionlimit(1000000)

class SCC:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.graph_rev = [[] for _ in range(n)]
        self.already = [False]*n
    
    def add_edge(self, fr, to):
        if fr == to:
            return
        self.graph[fr].append(to)
        self.graph_rev[to].append(fr)
    
    def dfs(self, node, graph):
        self.already[node] = True
        for n in graph[node]:
            if self.already[n]:
                continue
            self.dfs(n, graph)
        self.order.append(node)
    
    def first_dfs(self):
        self.already = [False]*self.n
        self.order = []
        for i in range(self.n):
            if self.already[i] == False:
                self.dfs(i, self.graph)
    
    def second_dfs(self):
        self.already = [False]*self.n
        self.ans = []
        for n in reversed(self.order):
            if self.already[n]:
                continue
            self.already[n] = True
            self.order = []
            self.dfs(n, self.graph_rev)
            self.order.reverse()
            self.ans.append(self.order)

    def scc(self):
        self.first_dfs()
        self.second_dfs()
        return self.ans


def main():
    n, m = map(int, input().split())
    scc = SCC(n)

    for i in range(m):
        a, b = map(int, input().split())
        scc.add_edge(a, b)
    
    scc_list = scc.scc()

    print(len(scc_list))
    for s in scc_list:
        print(len(s), end=" ")
        print(*s)

    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
class SCC:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.graph_rev = [[] for _ in range(n)]
        self.already = [False]*n
    
    def add_edge(self, fr, to):
        if fr == to:
            return
        self.graph[fr].append(to)
        self.graph_rev[to].append(fr)
    
    def dfs(self, node, graph):
        self.already[node] = True
        for n in graph[node]:
            if self.already[n]:
                continue
            self.dfs(n, graph)
        self.order.append(node)
    
    def first_dfs(self):
        self.already = [False]*self.n
        self.order = []
        for i in range(self.n):
            if self.already[i] == False:
                self.dfs(i, self.graph)
    
    def second_dfs(self):
        self.already = [False]*self.n
        self.ans = []
        for n in reversed(self.order):
            if self.already[n]:
                continue
            self.already[n] = True
            self.order = []
            self.dfs(n, self.graph_rev)
            self.order.reverse()
            self.ans.append(self.order)

    def scc(self):
        self.first_dfs()
        self.second_dfs()
        return self.ans


def main():
    n, m = map(int, input().split())
    scc = SCC(n)

    for i in range(m):
        a, b = map(int, input().split())
        scc.add_edge(a, b)
    
    scc_list = scc.scc()
    print(len(scc_list))
    for s in scc_list:
        print(len(s), end=" ")
        print(*s)

        
    
if __name__ == "__main__":
    main()