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|  s 0  t 0  s 1  t 1 : s |E|-1  t |E|-1  Q  u 0  v 0  u 1  v 1 : u Q-1  v Q-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.  s i and t i represent source and target nodes of i -th edge (directed).  u i and v i 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

Solution (Python):
"""
強連結成分分解
"""

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_num , e_num = map(int, input().split())
edges = [[] for _ in range(v_num)]
reverse_edges = [[] for _ in range(v_num)]
for _ in range(e_num):
  s, t = map(int, input().split())
  edges[s].append(t)
  reverse_edges[t].append(s)


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


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

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

Solution (Python):
"""
強連結成分分解
"""

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)

def main():
  v_num , e_num = map(int, input().split())
  edges = [[] for _ in range(v_num)]
  reverse_edges = [[] for _ in range(v_num)]
  for _ in range(e_num):
    s, t = map(int, input().split())
    edges[s].append(t)
    reverse_edges[t].append(s)
  
  
  order = []
  visited = [False] * v_num
  for v in range(v_num):
    if not visited[v]:
      dfs(v, visited, edges, order)
  order.reverse()
  
  
  visited = [False] * v_num
  parent = [i for i in range(v_num)]
  for v in order:
    if not visited[v]:
      search_strongly_connection(v, visited, reverse_edges, parent, v)
  
  q_num = int(input())
  for _ in range(q_num):
    u, v = map(int, input().split())
    print(1 if parent[u] == parent[v] else 0)

main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def scc(n, e, re):

    v = [None] * n
    t = []
    def dfs(i):
        v[i] = 0
        for b in e[i]:
            if v[b] is None:
                dfs(b)
        t.append(i)

    for i in range(n):
        if v[i] is None:
            dfs(i)

    r = [None] * n
    def dfs2(i, p):
        r[i] = p
        for b in re[i]:
            if r[b] is None:
                dfs2(b, p)

    for c in t[::-1]:
        if r[c] is None:
            dfs2(c, c)

    return r

def main():
    n,m = LI()
    st = [LI() for _ in range(m)]
    q = I()
    uv = [LI() for _ in range(q)]

    e = collections.defaultdict(set)
    re = collections.defaultdict(set)
    for s,t in st:
        e[s].add(t)
        re[t].add(s)

    r = scc(n, e, re)
    rr = []
    for u,v in uv:
        if r[u] == r[v]:
            rr.append(1)
        else:
            rr.append(0)

    return JA(rr, "\n")


print(main())

Solution (Python):
def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a].append(b) for a, b in ab]

    def scc(g_temp):
        g, n = [set(i) for i in g_temp], len(g_temp)
        rg, cmp_, vs = [[] for _ in [0]*n], [0]*n, []
        for v1, v_list in enumerate(g):
            for v2 in v_list:
                rg[v2].append(v1)
        used = [False]*n
        for v in range(n):
            if not used[v]:
                q = [v]
                while q:
                    v = q[-1]
                    used[v] = True
                    while g[v]:
                        i = g[v].pop()
                        if not used[i]:
                            q.append(i)
                            break
                    else:
                        q.pop()
                        vs.append(v)
        used = [False]*n
        kk = [-1]
        for i in range(len(vs)-1, -1, -1):
            if not used[vs[i]]:
                q = [vs[i]]
                kk[0] += 1
                while q:
                    v, k = q[-1], kk[0]
                    used[v], cmp_[v] = True, k
                    while rg[v]:
                        i = rg[v].pop()
                        if not used[i]:
                            q.append(i)
                            break
                    else:
                        q.pop()
        k = kk[0]
        g2 = [set() for _ in [0]*(k+1)]
        for v1, v_list in enumerate(g_temp):
            for v2 in v_list:
                g2[cmp_[v1]].add(cmp_[v2])
        for v, v_set in enumerate(g2):
            if v in v_set:
                g2[v].remove(v)
        g2 = [list(v) for v in g2]
        return g2, cmp_

    s = scc(g)[1]
    q = int(input())
    for i in range(q):
        c, d = map(int, input().split())
        if s[c] == s[d]:
            print(1)
        else:
            print(0)


main()

Solution (Python):

def scc_decomposition(G):
    n = len(G)
    G_rev = [[] for _ in range(n)]
    for u in range(n):
        for v in G[u]:
            G_rev[v].append(u)

    
    vs = []
    visited = [False] * n
    used = [False] * n
    for u in range(n):
        if visited[u]:
            continue
        stack = [u]
        while stack:
            v = stack.pop()
            if used[v]:
                continue
            if not visited[v]:
                visited[v] = True
            else:
                vs.append(v)
                used[v] = True
                continue
            stack.append(v)
            for c in G[v]:
                if not visited[c]:
                    stack.append(c)

    
    visited = [False] * n
    component = [-1] * n
    for i, u in enumerate(vs[::-1]):
        if visited[u]:
            continue
        stack = [u]
        while stack:
            v = stack.pop()
            visited[v] = True
            component[v] = i
            for c in G_rev[v]:
                if not visited[c]:
                    stack.append(c)

    return component

class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, x):
        r = x
        while self.parent[r] != r:
            r = self.parent[r]
        while self.parent[x] != r:
            x, self.parent[x] = self.parent[x], r
        return r

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        return self.size[self.find(x)]

V, E = map(int, input().split())
G = [[] for _ in range(V)]
for _ in range(E):
    s, t = map(int, input().split())
    G[s].append(t)
component = scc_decomposition(G)
uf = UnionFind(2 * V)
for v in range(V):
    uf.unite(v, V + component[v])
Q = int(input())
for _ in range(Q):
    u, v = map(int, input().split())
    if uf.same(u, v):
        print(1)
    else:
        print(0)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m = map(int, input().split())
    E = [[] for _ in range(n)]
    rev = [[] for _ in range(n)]
    outdeg = [0] * n
    for _ in range(m):
        u, v = map(int, input().split())
        E[u].append(v)
        rev[v].append(u)
        outdeg[u] += 1

    order = []
    used = [False] * n
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    def dfs(v):
        if used[v]:
            return
        used[v] = True
        for nv in E[v]:
            dfs(nv)
        order.append(v)
    any(dfs(v) for v in range(n))
    order.reverse()
    color = [-1] * n
    ans = []
    cnt = -1
    for v in order:
        if color[v] != -1:
            continue
        cnt += 1
        color[v] = cnt
        stack = [v]
        while stack:
            v = stack.pop()
            for nv in rev[v]:
                if color[nv] != -1:
                    continue
                color[nv] = cnt
                stack.append(nv)

    for _ in range(int(input())):
        u, v = map(int, input().split())
        print(int(color[u] == color[v]))
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class StronglyConnectedComponents:
    def __init__(self,N):
        self.N = N
        self.G = [[] for _ in range(self.N)]
        self.rG = [[] for _ in range(self.N)]
        self.group = [1] * self.N
        self.order = []
    
    def add_edge(self,u,v): 
        self.G[u].append(v)
        self.rG[v].append(u)
    
    def build(self):
        stack = []
        for s in range(self.N):
            if self.group[s] > 0:
                stack.append(s + 1)
                while stack:
                    v = stack.pop()
                    if v < 0:
                        self.order.append(- v - 1)
                    else:
                        if self.group[v - 1] > 0:
                            stack.append(-v)
                            self.group[v - 1] = -1
                            for e in self.G[v - 1]:
                                stack.append(e + 1)
        
        cnt = 0
        for s in self.order[::-1]:
            if self.group[s] < 0:
                stack.append(s)
                self.group[s] = cnt
                while stack:
                    v = stack.pop()
                    for e in self.rG[v]:
                        if self.group[e] < 0:
                            self.group[e] = cnt
                            stack.append(e)
                cnt += 1
    
    def __getitem__(self,i):
        if 0 <= i < self.N:
            return self.group[i]
        else:
            raise ValueError("StrongglyConnectedComponents index out of range")

def main():
    V,E = map(int,input().split())
    scc = StronglyConnectedComponents(V)
    for _ in range(E):
        a,b = map(int,input().split())
        scc.add_edge(a,b)
    scc.build()

    Q = int(input())
    ans = []
    for _ in range(Q):
        u,v = map(int,input().split())
        if scc[u] == scc[v]:
            ans.append('1')
        else:
            ans.append('0')
    print('\n'.join(ans))
if __name__ == '__main__':
    main()

Solution (Python):
mod = 1000000007
eps = 10**-9


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

    from collections import deque

    
    
    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)

        
        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
            
            while st:
                v = st.pop()
                for u in adj_rev[v]:
                    if seen[u]:
                        continue
                    
                    seen[u] = 1
                    compressed[u] = num
                    st.append(u)

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

Solution (Python):
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




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.append((v, i + 1))
                stack.append((u, 0))
                break
            else:
                
                pre_order.append(v)

    
    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')

Solution (Python):
class Graph(): 
    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)))

Solution (Python):









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)) 
Q = int(sys.stdin.readline())
uv = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(Q)) 


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)

Solution (Python):

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

Solution (Python):
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

        
        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)

        
        self.post_order = []
        self.used = [False] * self.n
        for v in range(self.n):
            if not self.used[v]:
                self._dfs(v)

        
        
        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

        
        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)

Solution (Python):
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)

Solution (Python):

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)

Solution (Python):
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)

Solution (Python):
import sys
sys.setrecursionlimit(200000)
from collections import deque

def addEdge(g, a, z):
    g[0][a].append(z)
    g[1][z].append(a)


def initGraph(g, edgenum):
    g.append([])  
    g.append([])  
    for _ in range(edgenum):
        g[0].append(deque(list()))
    for _ in range(edgenum):
        g[1].append(deque(list()))

def dfs(g, v, visited, vs):
    
    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):
    
    
    visited[v] = True
    cmp[v] = k
    
    for i in range(len(g[1][v])):
        
        
        if visited[g[1][v][i]] is False:
            
            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
    
    for i in range(len(vs) - 1, -1, -1):
        
        
        if visited[vs[i]] is False:
            
            rdfs(g, vs[i], visited, cmp, k)
            k += 1
    
    return k

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

g = []  
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)