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: Accepted

Solution code:
from collections import deque
class csr:
    def __init__(self,N,edges):
        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 scc_graph:
    def __init__(self,N):
        self.N = N
        self.edges = []
    
    def add_edge(self,v,w):
        self.edges.append((v,w))

    def scc_ids(self):
        g = csr(self.N,self.edges)
        N = self.N
        now_ord = group_num = 0
        visited = deque()
        low = [0]*N
        order = [-1]*N
        ids = [0]*N
        parent = [-1]*N
        stack = deque()
        for i in range(N):
            if order[i] == -1:
                stack.append(i)
                stack.append(i)
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        visited.append(v)
                        for i in range(g.start[v],g.start[v+1]):
                            to = g.elist[i]
                            if order[to] == -1:
                                stack.append(to)
                                stack.append(to)
                                parent[to] = v
                            else:
                                low[v] = min(low[v],order[to])
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[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):
        group_num,ids = self.scc_ids()
        groups = [[] for _ in range(group_num)]
        for i,x in enumerate(ids):
            groups[x].append(i)
        return groups
    
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
N,M = map(int,readline().split())
ab = list(map(int,read().split()))
sg = scc_graph(N)

it = iter(ab)
for a,b in zip(it,it):
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(str(len(group))+' '+' '.join(map(str,group)))

Submission status: Accepted

Solution code:
from collections import deque
class csr:
    __slots__ = ['start','elist']
    def __init__(self,N,edges):
        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 scc_graph:
    __slots__ = ['N','edges']
    def __init__(self,N):
        self.N = N
        self.edges = []
    
    def add_edge(self,v,w):
        self.edges.append((v,w))

    def scc_ids(self):
        g = csr(self.N,self.edges)
        now_ord = group_num = 0
        visited = deque()
        low = [0]*self.N
        order = [-1]*self.N
        ids = [0]*self.N
        parent = [-1]*self.N
        stack = deque()
        for i in range(self.N):
            if order[i] == -1:
                stack.append(i)
                stack.append(i)
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        visited.append(v)
                        for i in range(g.start[v],g.start[v+1]):
                            to = g.elist[i]
                            if order[to] == -1:
                                stack.append(to)
                                stack.append(to)
                                parent[to] = v
                            else:
                                low[v] = min(low[v],order[to])
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[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):
        group_num,ids = self.scc_ids()
        groups = [[] for _ in range(group_num)]
        for i,x in enumerate(ids):
            groups[x].append(i)
        return groups
    
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
N,M = map(int,readline().split())
ab = list(map(int,read().split()))
sg = scc_graph(N)

it = iter(ab)
for a,b in zip(it,it):
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(str(len(group))+' '+' '.join(map(str,group)))

Submission status: Accepted

Solution code:
from collections import deque
class csr:
    __slots__ = ['start','elist']
    def __init__(self,N,edges):
        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 scc_graph:
    def __init__(self,N):
        self.N = N
        self.edges = []
    
    def add_edge(self,v,w):
        self.edges.append((v,w))

    def scc_ids(self):
        g = csr(self.N,self.edges)
        now_ord = group_num = 0
        visited = deque()
        low = [0]*self.N
        order = [-1]*self.N
        ids = [0]*self.N
        parent = [-1]*self.N
        stack = deque()
        for i in range(self.N):
            if order[i] == -1:
                stack.append(i)
                stack.append(i)
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        visited.append(v)
                        for i in range(g.start[v],g.start[v+1]):
                            to = g.elist[i]
                            if order[to] == -1:
                                stack.append(to)
                                stack.append(to)
                                parent[to] = v
                            else:
                                low[v] = min(low[v],order[to])
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[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):
        group_num,ids = self.scc_ids()
        groups = [[] for _ in range(group_num)]
        for i,x in enumerate(ids):
            groups[x].append(i)
        return groups
    
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
N,M = map(int,readline().split())
ab = list(map(int,read().split()))
sg = scc_graph(N)

it = iter(ab)
for a,b in zip(it,it):
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(str(len(group))+' '+' '.join(map(str,group)))

Submission status: Accepted

Solution code:
from collections import deque
class csr:
    def __init__(self,N,edges):
        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 scc_graph:
    def __init__(self,N):
        self.N = N
        self.edges = []
    
    def add_edge(self,v,w):
        self.edges.append((v,w))

    def scc_ids(self):
        g = csr(self.N,self.edges)
        now_ord = group_num = 0
        visited = deque()
        low = [0]*self.N
        order = [-1]*self.N
        ids = [0]*self.N
        parent = [-1]*self.N
        stack = deque()
        for i in range(self.N):
            if order[i] == -1:
                stack.append(i)
                stack.append(i)
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        visited.append(v)
                        for i in range(g.start[v],g.start[v+1]):
                            to = g.elist[i]
                            if order[to] == -1:
                                stack.append(to)
                                stack.append(to)
                                parent[to] = v
                            else:
                                low[v] = min(low[v],order[to])
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[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):
        group_num,ids = self.scc_ids()
        groups = [[] for _ in range(group_num)]
        for i,x in enumerate(ids):
            groups[x].append(i)
        return groups
    
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
N,M = map(int,readline().split())
ab = list(map(int,read().split()))
sg = scc_graph(N)

it = iter(ab)
for a,b in zip(it,it):
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(str(len(group))+' '+' '.join(map(str,group)))

Submission status: Accepted

Solution code:
from collections import deque
class csr:
    def __init__(self,N,edges):
        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 scc_graph:
    def __init__(self,N):
        self.N = N
        self.edges = []
    
    def add_edge(self,v,w):
        self.edges.append((v,w))

    def scc_ids(self):
        g = csr(self.N,self.edges)
        now_ord = group_num = 0
        visited = deque()
        low = [0]*self.N
        order = [-1]*self.N
        ids = [0]*self.N
        parent = [-1]*self.N
        for i in range(self.N):
            if order[i] == -1:
                stack = []
                stack.append(i)
                stack.append(i)
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        visited.append(v)
                        for i in range(g.start[v],g.start[v+1]):
                            to = g.elist[i]
                            if order[to] == -1:
                                stack.append(to)
                                stack.append(to)
                                parent[to] = v
                            else:
                                low[v] = min(low[v],order[to])
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[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):
        group_num,ids = self.scc_ids()
        groups = [[] for _ in range(group_num)]
        for i,x in enumerate(ids):
            groups[x].append(i)
        return groups
    
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
N,M = map(int,readline().split())
ab = list(map(int,read().split()))
sg = scc_graph(N)

it = iter(ab)
for a,b in zip(it,it):
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(str(len(group))+' '+' '.join(map(str,group)))

Submission status: Accepted

Solution code:
from collections import deque
class csr:
    def __init__(self,N,edges):
        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 scc_graph:
    def __init__(self,N):
        self.N = N
        self.edges = []
    
    def add_edge(self,v,w):
        self.edges.append((v,w))

    def scc_ids(self):
        g = csr(self.N,self.edges)
        now_ord = group_num = 0
        visited = deque()
        low = [0]*self.N
        order = [-1]*self.N
        ids = [0]*self.N
        parent = [-1]*self.N
        for i in range(self.N):
            if order[i] == -1:
                stack = deque()
                stack.append(i)
                stack.append(i)
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        visited.append(v)
                        for i in range(g.start[v],g.start[v+1]):
                            to = g.elist[i]
                            if order[to] == -1:
                                stack.append(to)
                                stack.append(to)
                                parent[to] = v
                            else:
                                low[v] = min(low[v],order[to])
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[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):
        group_num,ids = self.scc_ids()
        groups = [[] for _ in range(group_num)]
        for i,x in enumerate(ids):
            groups[x].append(i)
        return groups
    
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
N,M = map(int,readline().split())
ab = list(map(int,read().split()))
sg = scc_graph(N)

it = iter(ab)
for a,b in zip(it,it):
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(*([len(group)] + group))

Submission status: Accepted

Solution code:
from collections import deque
class csr:
    def __init__(self,N,edges):
        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 scc_graph:
    def __init__(self,N):
        self.N = N
        self.edges = []
    
    def add_edge(self,v,w):
        self.edges.append((v,w))

    def scc_ids(self):
        g = csr(self.N,self.edges)
        now_ord = group_num = 0
        visited = deque()
        low = [0]*self.N
        order = [-1]*self.N
        ids = [0]*self.N
        parent = [-1]*self.N
        for i in range(self.N):
            if order[i] == -1:
                stack = deque()
                stack.append(i)
                stack.append(i)
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        visited.append(v)
                        for i in range(g.start[v],g.start[v+1]):
                            to = g.elist[i]
                            if order[to] == -1:
                                stack.append(to)
                                stack.append(to)
                                parent[to] = v
                            else:
                                low[v] = min(low[v],order[to])
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[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):
        group_num,ids = self.scc_ids()
        groups = [[] for _ in range(group_num)]
        for i,x in enumerate(ids):
            groups[x].append(i)
        return groups
    
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
N,M = map(int,readline().split())
ab = list(map(int,read().split()))
sg = scc_graph(N)

it = iter(ab)
for a,b in zip(it,it):
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(str(len(group))+' '+' '.join(map(str,group)))

Submission status: Accepted

Solution code:
from collections import deque
class csr:
    def __init__(self,N,edges):
        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 scc_graph:
    def __init__(self,N):
        self.N = N
        self.edges = []
    
    def add_edge(self,v,w):
        self.edges.append((v,w))

    def scc_ids(self):
        g = csr(self.N,self.edges)
        now_ord = group_num = 0
        visited = deque()
        low = [0]*self.N
        order = [-1]*self.N
        ids = [0]*self.N
        parent = [-1]*self.N
        for i in range(self.N):
            if order[i] == -1:
                stack = deque()
                stack.append(i)
                stack.append(i)
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        visited.append(v)
                        for i in range(g.start[v],g.start[v+1]):
                            to = g.elist[i]
                            if order[to] == -1:
                                stack.append(to)
                                stack.append(to)
                                parent[to] = v
                            else:
                                low[v] = min(low[v],order[to])
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[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):
        group_num,ids = self.scc_ids()
        groups = [[] for _ in range(group_num)]
        for i,x in enumerate(ids):
            groups[x].append(i)
        return groups
    
import sys
input = sys.stdin.buffer.readline
N,M = map(int,input().split())
sg = scc_graph(N)
for i in range(M):
    a,b = map(int,input().split())
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(str(len(group))+' '+' '.join(map(str,group)))

Submission status: Accepted

Solution code:
import sys
range = xrange
input = raw_input
 
def find_SCC(coupl):
    SCC, S, P = [], [], []
    depth = [0] * len(coupl)
 
    stack = list(range(len(coupl)))
    while stack:
        node = stack.pop()
        if node < 0:
            d = depth[~node] - 1
            if P[-1] > d:
                SCC.append(S[d:])
                del S[d:], P[-1]
                for node in SCC[-1]:
                    depth[node] = -1
        elif depth[node] > 0:
            while P[-1] > depth[node]:
                P.pop()
        elif depth[node] == 0:
            S.append(node)
            P.append(len(S))
            depth[node] = len(S)
            stack.append(~node)
            stack += coupl[node]
    return SCC[::-1]
 
inp = [int(x) for x in sys.stdin.read().split()]; ii = 0
 
n = inp[ii]; ii += 1
m = inp[ii]; ii += 1
 
coupl = [[] for _ in range(n)]
for _ in range(m):
    u = inp[ii]; ii += 1
    v = inp[ii]; ii += 1
    coupl[u].append(v)
 
SCC = find_SCC(coupl)
out = [len(SCC)]
for scc in SCC:
    out.append(len(scc))
    for node in scc:
        out.append(node)
print ' '.join(str(x) for x in out)