Problem:


Strongly Connected Components

A direced graph is strongly connected if every two nodes are reachable from each other. In a strongly connected component of a directed graph, every two nodes of the component are mutually reachable.

Input

A directed graph G(V, E) and a sequence of queries where each query contains a pair of nodes u and v.

|V| |E|
s0 t0
s1 t1
:
s|E|-1 t|E|-1
Q
u0 v0
u1 v1
:
uQ-1 vQ-1

|V| is the number of nodes and |E| is the number of edges in the graph. The graph nodes are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target nodes of i-th edge (directed).

ui and vi represent a pair of nodes given as the i-th query.

Output

For each query, pinrt "1" if the given nodes belong to the same strongly connected component, "0" otherwise.

Constraints

1 ≤ |V| ≤ 10,000

0 ≤ |E| ≤ 30,000

1 ≤ Q ≤ 100,000

Sample Input 1

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

Sample Output 1

1
0
1
1



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


Sample output:
1
0
1
1

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    from collections import deque

    # compressed[v]: 縮約後のグラフで縮約前のvが属する頂点
    # num: 縮約後のグラフの頂点数
    def SCC(adj, adj_rev):
        N = len(adj) - 1
        seen = [0] * (N + 1)
        compressed = [0] * (N + 1)
        order = []

        for v0 in range(1, N + 1):
            if seen[v0]:
                continue
            st = deque()
            st.append(v0)
            while st:
                v = st.pop()
                if v < 0:
                    order.append(-v)
                else:
                    if seen[v]:
                        continue
                    seen[v] = 1
                    st.append(-v)
                    for u in adj[v]:
                        st.append(u)

        #print(order)
        seen = [0] * (N + 1)
        num = 0
        for v0 in reversed(order):
            if seen[v0]:
                continue
            num += 1
            st = deque()
            st.append(v0)
            seen[v0] = 1
            compressed[v0] = num
            #print(v0, num)
            while st:
                v = st.pop()
                for u in adj_rev[v]:
                    if seen[u]:
                        continue
                    #print([v, u])
                    seen[u] = 1
                    compressed[u] = num
                    st.append(u)

        return num, compressed

    # 縮約後のグラフを構築
    # 先にSCC()を実行してnum, compressedを作っておく
    def construct(adj, num, compressed):
        N = len(adj) - 1
        adj_compressed = [set() for _ in range(num + 1)]
        for v in range(1, N + 1):
            v_cmp = compressed[v]
            for u in adj[v]:
                u_cmp = compressed[u]
                if v_cmp != u_cmp:
                    adj_compressed[v_cmp].add(u_cmp)
        return adj_compressed

    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    adj_rev = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        a += 1
        b += 1
        adj[a].append(b)
        adj_rev[b].append(a)

    NN, compress = SCC(adj, adj_rev)
    ans = []
    Q = int(input())
    query = []
    for _ in range(Q):
        u, v = map(int, input().split())
        query.append((u, v))
        if compress[u+1] == compress[v+1]:
            ans.append(1)
        else:
            ans.append(0)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

def strongly_connected_components(graph):
    """
    強連結成分分解; SCC
    ret[v]: v のコンポーネント番号
    コンポーネント番号はトポロジカル順で前にある方が小さい
    Verify: https://atcoder.jp/contests/arc030/submissions/14035565
    :param list of (list of int) graph:
    :rtype: list of int
    """
    N = len(graph)

    rev_graph = [[] for _ in range(N)]
    for v in range(N):
        for u in graph[v]:
            rev_graph[u].append(v)

    # 帰りがけ順
    pre_order = []
    seen = [False] * N
    for v in range(N):
        if seen[v]:
            continue
        seen[v] = True
        stack = [(v, 0)]
        while stack:
            v, pos = stack.pop()
            for i in range(pos, len(graph[v])):
                u = graph[v][i]
                if seen[u]:
                    continue
                seen[u] = True
                # 中断して次の頂点を Stack に詰む
                stack.append((v, i + 1))
                stack.append((u, 0))
                break
            else:
                # 帰りがけ
                pre_order.append(v)

    # 帰りがけ順が遅い順に DFS
    cid = 0
    ret = [-1] * N
    seen = [False] * N
    for v in reversed(pre_order):
        if seen[v]:
            continue
        seen[v] = True
        stack = [v]
        while stack:
            v = stack.pop()
            ret[v] = cid
            for u in rev_graph[v]:
                if seen[u]:
                    continue
                seen[u] = True
                stack.append(u)
        cid += 1
    return ret


V, E = list(map(int, sys.stdin.buffer.readline().split()))
ST = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(E)]
Q = int(sys.stdin.buffer.readline())
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]

graph = [[] for _ in range(V)]
for s, t in ST:
    graph[s].append(t)
scc = strongly_connected_components(graph)
ans = []
for v, u in VU:
    ans.append(int(scc[v] == scc[u]))
print(*ans, sep='\n')

Submission status: Accepted

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.readline

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

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

res = []

Q = int(input())

for _ in range(Q):
    a, b = map(int, input().split())
    if group[a - 1] == group[b - 1]:
        res.append(1)
    else:
        res.append(0)

print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")

import sys,collections
sys.setrecursionlimit(100000)

INF = float("inf")

V,E = map(int,sys.stdin.readline().split())
st = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(E)) # multi line with multi param
Q = int(sys.stdin.readline())
uv = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(Q)) # multi line with multi param
#st = [[0,1],[0,2],[1,2],[2,3]]
#uv = [[0,1],[0,2],[1,2],[2,3]]
G = {i:[] for i in range(V)}
rG = {i:[] for i in range(V)}

for s,t in st:
    G[s].append(t)
    rG[t].append(s)

def dfs(current):
    visited.add(current)
    for nex in G[current]:
        if not nex in visited: dfs(nex)
    post_order.append(current)

def rdfs(current,k):
    visited.add(current)
    topological_order[current]=k
    for nex in rG[current]:
        if not nex in visited: rdfs(nex,k)

visited = set()
post_order = []
for i in range(V):
    if not i in visited: dfs(i)

topological_order = [0]*V
visited = set()

k = 0
for i in post_order[::-1]:
    if not i in visited:
        rdfs(i,k)
        k += 1

for u,v in uv:
    if topological_order[u] == topological_order[v]:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:

import sys
import math
import bisect
import heapq
import copy
sys.setrecursionlimit(1000000)
from collections import deque
from itertools import permutations

class SCC:

    def __init__(self,n):
        self.n = n
        self.Edge = [[] for _ in range(n)]
        self.REdge = [[] for _ in range(n)]
        self.vs = []
        self.used = [False]*n
        self.order = [0]*n

    def add_edge(self,from_,to):
        self.Edge[from_].append(to)
        self.REdge[to].append(from_)

    def dfs(self,v):
        self.used[v] = True
        for u in self.Edge[v]:
            if not self.used[u]:
                self.dfs(u)
        self.vs.append(v)

    def rdfs(self,v,k):
        self.used[v] = True
        self.order[v] = k
        for u in self.REdge[v]:
            if not self.used[u]:
                self.rdfs(u,k)

    def compute(self):
        self.used = [False]*self.n
        self.vs.clear()
        for i in range(self.n):
            if not self.used[i]:
                self.dfs(i)
        self.used = [False]*self.n
        k = 0
        for i in reversed(self.vs):
            if not self.used[i]:
                self.rdfs(i,k)
            k+=1
        return k


def main():
    v,e = map(int,input().split())
    scc = SCC(v) 
    for _ in range(e):
        a,b = map(int,input().split())
        scc.add_edge(a,b)
    k = scc.compute()
    n = int(input())
    for _ in range(n):
        a,b = map(int,input().split())
        print (int(scc.order[a]==scc.order[b]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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


class StronglyConnectedComponents:
    """与えられた有向グラフに対して強連結成分分解する
    label: 分解されたグラフの個数
    group: 強連結成分のグループ分け番号
    """
    def __init__(self, graph):
        self.n = len(graph)
        self.graph = graph
        self.out_degree = [len(graph[i]) for i in range(n)]
        self.label = 0
        self.group = [-1] * self.n

        # 逆辺を用いたグラフ(rev_graph)の構築
        self.rev_graph = [[] for i in range(self.n)]
        for a in range(self.n):
            for b in graph[a]:
                self.rev_graph[b].append(a)

        # graph上での帰りがけ順(post_order)の構築
        self.post_order = []
        self.used = [False] * self.n
        for v in range(self.n):
            if not self.used[v]:
                self._dfs(v)

        # 帰りがけ順の逆順で走査し、
        # 未訪問かつrev_graph上でたどり着ける頂点は強連結である
        for v in reversed(self.post_order):
            if self.group[v] == -1:
                self._rev_dfs(v, self.label)
                self.label += 1

    def _dfs(self, v):
        st1 = [v, 0]
        while st1:
            v, ind = st1[-2], st1[-1]
            if not ind and self.used[v]:
                st1.pop()
                st1.pop()
            else:
                self.used[v] = True
                if ind < self.out_degree[v]:
                    st1[-1] += 1
                    st1.append(graph[v][ind])
                    st1.append(0)
                else:
                    st1.pop()
                    self.post_order.append(st1.pop())

    def _rev_dfs(self, v, label):
        st = [v]
        self.group[v] = label
        while st:
            v = st.pop()
            for nxt_v in self.rev_graph[v]:
                if self.group[nxt_v] >= 0:
                    continue
                st.append(nxt_v)
                self.group[nxt_v] = label

    def construct(self):
        """縮約グラフ(red_graph)と縮約された頂点が含む元の頂点(red_comps)を求める"""
        self.red_graph = [set() for i in range(self.label)]
        self.red_comps = [[] for i in range(self.label)]

        for v in range(self.n):
            lb = self.group[v]
            for nxt_v in self.graph[v]:
                nxt_lb = self.group[nxt_v]
                if lb == nxt_lb:
                    continue
                self.red_graph[lb].add(nxt_lb)
            self.red_comps[lb].append(v)

        return self.red_graph, self.red_comps

    def tp_sort(self):
        """縮約グラフのトポロジカル順を求める"""
        red_n = len(self.red_graph)
        degree = [0] * red_n
        for v in range(red_n):
            for nxt_v in self.red_graph[v]:
                degree[nxt_v] += 1

        # 入次数が0の頂点を初期値状態とする
        res = [i for i in range(red_n) if degree[i] == 0]
        q = res[0:]
        while q:
            v = q.pop()
            for nxt_v in self.red_graph[v]:
                degree[nxt_v] -= 1
                if degree[nxt_v] == 0:
                    q.append(nxt_v)
                    res.append(nxt_v)
        return res


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]

graph = [[] for i in range(n)]
for a, b in info:
    graph[a].append(b)

scc = StronglyConnectedComponents(graph)
group = scc.group

for u, v in query:
    if group[u] == group[v]:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def dfs(v, visited, edges, order):
  visited[v] = True
  for to in edges[v]:
    if not visited[to]:
      dfs(to, visited, edges, order)
  order.append(v)

def search_strongly_connection(v, visited, reverse_edges, parent, num):
  visited[v] = True
  for to in reverse_edges[v]:
    if not visited[to]:
      parent[to] = num
      search_strongly_connection(to, visited, reverse_edges, parent, num)


v,e=map(int,input().split())
edges=[[] for _ in range(v)]
reverse_edges = [[] for _ in range(v)]
#有向グラフ
for _ in range(e):
    s,t=map(int,input().split())
    edges[s].append(t)
    reverse_edges[t].append(s)

order=[]
visited=[False]*v
for i in range(v):
    if not visited[i]:
        dfs(i,visited,edges,order)
order.reverse()

visited=[False]*v
parent=[i for i in range(v)]
for i in order:
    if not visited[i]:
        search_strongly_connection(i,visited,reverse_edges,parent,i)

q=int(input())
for _ in range(q):
    u,v=map(int,input().split())
    print(1 if parent[u]==parent[v] else 0)

Submission status: Accepted

Solution code:
#GRL_3_C
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def scc():
    order = []
    visited = [False]*N
    
    def dfs(v):
        visited[v] = True
        
        for nv in G[v]:
            if not visited[nv]:
                dfs(nv)
        
        order.append(v)
    
    for i in range(N):
        if not visited[i]:
            dfs(i)
    
    visited = [False]*N
    group = [-1]*N
    label = 0
    
    def rdfs(v, label):
        group[v] = label
        visited[v] = True
        
        for nv in RG[v]:
            if not visited[nv]:
                rdfs(nv, label)
    
    for v in reversed(order):
        if not visited[v]:
            rdfs(v, label)
            label += 1
            
    return label, group

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

for _ in range(M):
    s, t = map(int, input().split())
    G[s].append(t)
    RG[t].append(s)
    
_, group = scc()

Q = int(input())

for _ in range(Q):
    u, v = map(int, input().split())
    
    if group[u]==group[v]:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
from collections import deque

setrecursionlimit(20001)

def read():
    v, e = tuple([int(e) for e in input().split()])
    adj = [[] for _ in range(v)]
    for _ in range(e):
        v_from, v_to = tuple([int(e) for e in input().split()])
        adj[v_from].append(v_to)

    return adj, v


def find_strong_components(adj, n):
    id = [0 for _ in range(n + 1)]
    low_link = [0 for _ in range(n)]
    mark = [False for _ in range(n)]
    in_stack = [False for _ in range(n)]
    st = deque()
    
    for v in range(n):
        if mark[v]: continue
        dfs(v, mark, id, low_link, adj, in_stack, st)
    return low_link

def dfs(v, mark, id, low_link, adj, in_stack, st):
    mark[v] = True
    in_stack[v] = True
    low_link[v] = id[v] = id[-1]
    id[-1]+=1

    st.append(v)
    for n_v in adj[v]:
        if not mark[n_v]:
            dfs(n_v, mark, id, low_link, adj, in_stack, st)
        if in_stack[n_v]:
            low_link[v] = min(low_link[v], low_link[n_v])

    if id[v] == low_link[v]:
        while st:
            top_v = st.pop() 
            low_link[top_v] = id[v]
            in_stack[top_v] = False
            if top_v == v:
                break

def write(low_link):
    q = int(input())
    for _ in range(q):
        v1, v2 = tuple([int(e) for e in input().split()])
        if low_link[v1] == low_link[v2]:
            print('1')
        else:
            print('0')

adj, n = read()
low_link = find_strong_components(adj, n)
write(low_link)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
from collections import deque
# a-zに正方向と逆辺を張る
def addEdge(g, a, z):
    g[0][a].append(z)
    g[1][z].append(a)

# グラフの初期化
def initGraph(g, edgenum):
    g.append([])  # [0] 正方向のグラフ
    g.append([])  # [1] 逆方向のグラフ
    for _ in range(edgenum):
        g[0].append(deque(list()))
    for _ in range(edgenum):
        g[1].append(deque(list()))

def dfs(g, v, visited, vs):
    # 正方向のDFS
    visited[v] = True
    for i in range(len(g[0][v])):
        if visited[g[0][v][i]] is False:
            dfs(g, g[0][v][i], visited, vs)
    vs.append(v)

def rdfs(g, v, visited, cmp, k):
    # 逆方向のDFS
    # kがcall元に指定される連結成分の通し番号
    visited[v] = True
    cmp[v] = k
    # 指定したノードの逆辺をたどる
    for i in range(len(g[1][v])):
        # print("go? {0}".format(g[1][v][i]))
        # 逆辺の先がrDFSで到達できないときのみ
        if visited[g[1][v][i]] is False:
            # print("yes")
            rdfs(g, g[1][v][i], visited, cmp, k)

def scc(g, cmp):
    vs = []  # 帰りがけのリスト
    visited = [False] * len(g[0])
    cmp.extend([None] * len(g[0]))
    for i in range(len(g[0])):
        if visited[i] is False:
            dfs(g, i, visited, vs)

    visited = [False] * len(g[1])
    k = 0
    # pprint(vs)
    for i in range(len(vs) - 1, -1, -1):
        # print("vited: i={0} vs[i] = {1}".format(i, vs[i]))
        # print(visited)
        if visited[vs[i]] is False:
            # print("rdfs [{0}]".format(i))
            rdfs(g, vs[i], visited, cmp, k)
            k += 1
    # pprint(vs)
    return k

vCount, e = map(int, input().split())

g = []  # グラフ。[0] = 正方向のグラフ。 [1] = 逆方向のグラフ
v = []  # 辺
cmp = []

from pprint import pprint
initGraph(g, edgenum=vCount)
for _ in range(e):
    x, y = map(int, input().split())
    addEdge(g, x, y)

scc(g, cmp)

for _ in range(int(input())):
    x, y = map(int, input().split())
    print(1 if cmp[x] == cmp[y] else 0)

Submission status: Accepted

Solution code:
"""
強連結成分分解（Kosarju）
グラフ g, 逆辺グラフ rg の強連結成分分解をする

gp[i] = 頂点 i が属するグループ番号
g_scc: sccされたグラフ（辺はsetでとっていることに注意）
   g_scc は,N-1,N-2,..の順で見るとDAGになる
"""
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

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

# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
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 = [int(i) for i in readline().split()]
    g[a].append(b)
    rg[b].append(a)

gp, scc = StrongConnectedComponent(g,rg)
q = int(readline())
for _ in range(q):
    a,b = [int(i) for i in readline().split()]
    if gp[a] == gp[b]: print(1)
    else: print(0)

Submission status: Accepted

Solution code:
def strongly_connected_components(E):
    N = len(E)
    postorder = []
    visited = set([])
    
    def reverse_edge(E):
        result = [[] for _ in range(len(E))]
        for v, neighbor in enumerate(E):
            for n in neighbor:
                result[n].append(v)
        return result

    def dfs(E, s):
        postorder = [] # a dfs postordering of each vertex
        nonlocal visited
        stack = [(s, -1, 0)] # (vertex, parent, status)
        while stack:
            v, p, st = stack.pop()
            if st == 0 and v not in visited: # visited v for the first time
                visited |= {v}
                n_children = 0
                for u in E[v]:
                    if u in visited:
                        continue
                    if n_children == 0:
                        stack += [(v, p, 2), (u, v, 0)]
                        n_children += 1
                    else:
                        stack += [(v, p, 1), (u, v, 0)]
                        n_children += 1
                if n_children == 0: # v is a leaf
                    postorder.append(v)
            elif st == 0 and v in visited: # the edge (v, p) is a back edge
                continue
            elif st == 1: # now searching
                continue
            else: # search finished
                postorder.append(v)
        return postorder

    for v in range(N):
        if v not in visited:
            order = dfs(E, v)
            postorder += order
    
    reverse_E = reverse_edge(E)
    
    scc = [N] * N
    visited = set([])
    k = 0
    while postorder:
        v = postorder.pop()
        if scc[v] == N:
            order = dfs(reverse_E, v)
            for u in order: scc[u] = k
            k += 1
    return scc

N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    s, t = map(int, input().split())
    E[s].append(t)
scc = strongly_connected_components(E)
Q = int(input())
for _ in range(Q):
    u, v = map(int, input().split())
    print(1 if scc[u] == scc[v] else 0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2 * 10 ** 5)


class StronglyConnectedComponets:
    def __init__(self, n: int) -> None:
        self.n = n
        self.edges = [[] for _ in range(n)]
        self.rev_edeges = [[] for _ in range(n)]
        self.vs = []
        self.order = [0] * n
        self.used = [False] * n

    def add_edge(self, from_v: int, to_v: int) -> None:
        self.edges[from_v].append(to_v)
        self.rev_edeges[to_v].append(from_v)

    def dfs(self, v) -> None:
        self.used[v] = True
        for child in self.edges[v]:
            if not self.used[child]:
                self.dfs(child)
        self.vs.append(v)

    def rdfs(self, v, k) -> None:
        self.used[v] = True
        self.order[v] = k
        for child in self.rev_edeges[v]:
            if not self.used[child]:
                self.rdfs(child, k)

    def run(self) -> int:
        self.used = [False] * self.n
        self.vs.clear()
        for v in range(self.n):
            if not self.used[v]:
                self.dfs(v)
        self.used = [False] * self.n
        k = 0
        for v in reversed(self.vs):
            if not self.used[v]:
                self.rdfs(v, k)
                k += 1
        return k


def aoj():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_C
    V, E = map(int, input().split())
    scc = StronglyConnectedComponets(V)
    for _ in range(E):
        u, v = map(int, input().split())
        scc.add_edge(u, v)
    scc.run()
    for _ in range(int(input())):
        u, v = map(int, input().split())
        print(int(scc.order[u] == scc.order[v]))


if __name__ == "__main__":
    aoj()

Submission status: Accepted

Solution code:
#非再帰
import sys
def scc(Edge):
    N = len(Edge)
    Edgeinv = [[] for _ in range(N)]
    for vn in range(N):
        for vf in Edge[vn]:
            Edgeinv[vf].append(vn)
    
    used = [False]*N
    dim = [len(Edge[i]) for i in range(N)]
    order = []
    for st in range(N):
        if not used[st]:
            stack = [st, 0]
            while stack:
                vn, i = stack[-2], stack[-1]   
                if not i and used[vn]:
                    stack.pop()
                    stack.pop()
                else:
                    used[vn] = True
                    if i < dim[vn]:
                        stack[-1] += 1
                        stack.append(Edge[vn][i])
                        stack.append(0)
                    else:
                        stack.pop()
                        order.append(stack.pop())
    res = [None]*N
    used = [False]*N
    cnt = -1
    for st in order[::-1]:
        if not used[st]:
            cnt += 1
            stack = [st]
            res[st] = cnt
            used[st] = True
            while stack:
                vn = stack.pop()
                for vf in Edgeinv[vn]:
                    if not used[vf]:
                        used[vf] = True
                        res[vf] = cnt
                        stack.append(vf)
    M = cnt+1
    components = [[] for _ in range(M)]
    for i in range(N):
        components[res[i]].append(i)
    tEdge = [[] for _ in range(M)]
    teset = set()
    for vn in range(N):
        tn = res[vn]
        for vf in Edge[vn]:
            tf = res[vf]
            if tn*M + tf not in teset:
                teset.add(tn*M + tf)
                tEdge[tn].append(tf)
    return res, components, tEdge
        
V, E = map(int, input().split())
Edge = [[] for _ in range(V)]
for _ in range(E):
    a, b = map(int, sys.stdin.readline().split())
    Edge[a].append(b)
R, com, _ = scc(Edge)
Q = int(input())
for _ in range(Q):
    a, b = map(int, sys.stdin.readline().split())
    if R[a] == R[b]:
        sys.stdout.write('1\n')
    else:
        sys.stdout.write('0\n')

Submission status: Accepted

Solution code:
#蟻本参照
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
##redline,recursionlimit変更
v,e = map(int, input().split( ))

E = [[] for _ in range(v)]
revE = [[] for _ in range(v)]
used = [0]*v
kaeri = []
topo = [-1 for _ in range(v)]

for _ in range(e):
    s,t = map(int, input().split( ))
    E[s].append(t)
    revE[t].append(s)

q = int(input())

############
def dfs(v):
    used[v] = 1
    for u in E[v]:
        if not used[u]:
            dfs(u)
    kaeri.append(v)
    
def re_dfs(v,k):
    used[v] = 1
    topo[v] = k
    for u in revE[v]:
        if not used[u]:
            re_dfs(u,k)
###
for u in range(v):
    if not used[u]:
        dfs(u)
kaeri.reverse()        


used = [0]*v
k = 0
for u in kaeri:
    if not used[u]:
        k+=1
        re_dfs(u,k)
#print(topo)
for _ in range(q):
    u,v = map(int, input().split( ))
    if topo[u]==topo[v]:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)


def f_dfs(i: int) -> None:
    global f_edges, counter
    visited[i] = True
    for edge in f_edges[i]:
        if visited[edge]:
            continue
        f_dfs(edge)
    finish_order[i] = (counter, i)
    counter += 1


def b_dfs(i, group):
    global b_edges, groups
    visited[i] = True
    groups[i] = group
    for edge in b_edges[i]:
        if visited[edge]:
            continue
        b_dfs(edge, group)


if __name__ == "__main__":
    n, m = map(int, input().split())

    f_edges = [set() for _ in range(n)]  # type: ignore
    b_edges = [set() for _ in range(n)]  # type: ignore

    for _ in range(m):
        s, t = map(lambda x: int(x), input().split())
        f_edges[s].add(t)
        b_edges[t].add(s)

    visited = [False] * n
    finish_order = [(0, 0)] * n
    counter = 0

    for i in range(n):
        if not visited[i]:
            f_dfs(i)

    visited = [False] * n
    groups = [0] * n
    group = 0

    for d, i in sorted(finish_order, reverse=True):  # type: ignore
        if not visited[i]:
            b_dfs(i, group)
            group += 1

    q = int(input())
    for _ in range(q):
        u, v = map(lambda x: int(x), input().split())
        print(int(groups[u] == groups[v]))