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):
"""
強連結成分分解（Kosarju）
グラフ g, 逆辺グラフ rg の強連結成分分解をする

gp[i] = 頂点 i が属するグループ番号
g_scc: sccされたグラフ（辺はsetでとっていることに注意）
   g_scc は,N-1,N-2,..の順で見るとDAGになる
"""
def StrongConnectedComponent(g,rg):
    S = [] 
    
    q = []
    n = len(g)
    gp = [0]*n 
    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)
    
    
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(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








import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read



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)

Solution (Python):
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 = [] 
        nonlocal visited
        stack = [(s, -1, 0)] 
        while stack:
            v, p, st = stack.pop()
            if st == 0 and v not in visited: 
                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: 
                    postorder.append(v)
            elif st == 0 and v in visited: 
                continue
            elif st == 1: 
                continue
            else: 
                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)

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

Solution (Python):

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

Solution (Python):

import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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)

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

Solution (Python):
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)]  
    b_edges = [set() for _ in range(n)]  

    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):  
        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]))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
class Scc:
    def __init__(self, Edge):
        self.Edge = Edge
        self.N = len(Edge)
        self.Edgeinv = [[] for _ in range(self.N)]
    
    def decomposition(self):
        for i in range(self.N):
            for e in Edge[i]:
                self.Edgeinv[e].append(i)
        
        self.order = []
        self.used = set()
        for i in range(self.N):
            if i not in self.used:
                self.dfs1(i)
        
        self.res = [None]*self.N
        self.cnt = -1
        
        self.used = set()
        for v in self.order[::-1]:
            if v not in self.used:
                self.cnt += 1
                self.dfs2(v)
         
        n = self.cnt + 1
        components = [[] for _ in range(n)]
        for i in range(self.N):
            components[self.res[i]].append(i)
         
        cEdge = [[] for _ in range(n)]
        cset = set()
        for i in range(self.N):
            for e in Edge[i]:
                if self.res[i] != self.res[e] and self.res[i] + self.N*self.res[e] not in cset:
                    cset.add(self.res[i] + self.N*self.res[e])
                    cEdge[self.res[i]].append(self.res[e])
         
        return self.res, components, cEdge
    
    def dfs1(self, v):
        self.used.add(v)
        for vf in self.Edge[v]:
            if vf not in self.used:
                self.used.add(vf)
                self.dfs1(vf)
        self.order.append(v)
    
    def dfs2(self, v):
        self.used.add(v)
        self.res[v] = self.cnt
        stack = [v]
        while stack:
            vn = stack.pop()
            for vf in self.Edgeinv[vn]:
                if vf not in self.used:
                    self.used.add(vf)
                    self.res[vf] = self.cnt
                    stack.append(vf)
        
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)

G = Scc(Edge)
R, _, _ = G.decomposition()
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')

Solution (Python):

def input(f):
    global V, E, s, t, Q, u, v
    
    V, E = map(int, f.readline().split())
    s = [None for _ in range(E)]
    t = [None for _ in range(E)]
    for i in range(E):
        s[i], t[i] = map(int, f.readline().split())
        
    Q = int(f.readline())
    u = [None for _ in range(Q)]
    v = [None for _ in range(Q)]
    for i in range(Q):
        u[i], v[i] = map(int, f.readline().split())

import sys
sys.setrecursionlimit(1000000)

def solve():
    G = [[] for _ in range(V)]
    G_inv = [[] for _ in range(V)]
    for i in range(E):
        G[s[i]].append(t[i])
        G_inv[t[i]].append(s[i])

    def find_order():
        order = []
        used = [False for _ in range(V)]
        def rec(cur):
            if used[cur]:
                return
            used[cur] = True
            for nxt in G[cur]:
                rec(nxt)
            order.append(cur)
        
        for i in range(V):
            rec(i)
        
        return reversed(order)

    def decomp(order):
        groups = [None for _ in range(V)]
        used = [False for _ in range(V)]
        def rec(cur, group_id):
            if used[cur]:
                return
            used[cur] = True
            groups[cur] = group_id
            for nxt in G_inv[cur]:
                rec(nxt, group_id)
        
        group_id = 0
        for start in order:
            if used[start]:
                continue
            rec(start, group_id)
            group_id += 1
        
        return groups

    order = find_order()
    groups = decomp(order)

    for i in range(Q):
        if groups[u[i]] == groups[v[i]]:
            print('1')
        else:
            print('0')

with open('/dev/stdin') as f:
    input(f)
    solve()

Solution (Python):
import sys

sys.setrecursionlimit(int(1e6))

n, m = map(int, input().split())

graph = {}
graph_rev = {}

for i in range(m):
    s, t = map(int, input().split())
    if s not in graph:
        graph[s] = set()
    graph[s].add(t)
    if t not in graph_rev:
        graph_rev[t] = set()
    graph_rev[t].add(s)

order = []
visited = set()


def dfs1(i):
    visited.add(i)
    if i in graph:
        for t in graph[i]:
            if t not in visited:
                dfs1(t)
    order.append(i)


for i in range(n):
    if i not in visited:
        dfs1(i)

group = [-1] * n
visited.clear()


def dfs2(i, g):
    visited.add(i)
    group[i] = g
    if i in graph_rev:
        for t in graph_rev[i]:
            if t not in visited:
                dfs2(t, g)


group_id = 0

while len(order) > 0:
    v = order.pop()
    if v in visited:
        continue
    dfs2(v, group_id)
    group_id += 1

q = int(input())
ans = []

for i in range(q):
    u, v = map(int, input().split())
    ans.append(1) if group[u] == group[v] else ans.append(0)

for a in ans:
    print(a)

Solution (Python):
import sys

sys.setrecursionlimit(1000000000)

maxv,maxe = map(int , input().split())
g = [[] for i in range(maxv)] 
rg = [[] for i in range(maxv)] 
vs =  [0 for i in range(maxv)] 
used = [0 for i in range(maxv)] 
compo = [0 for i in range(maxv)] 

for i in range(maxe):
    s,t = map(int , input().split())
    g[s].append(t)
    rg[t].append(s)

def dfs(v):
    used[v] = 1
    for nextv in g[v]:
        if(not used[nextv]) :dfs(nextv)
    vs.append(v)

def rdfs(v,k):
    used[v] = 1
    compo[v] = k
    for nextv in rg[v]:
        if (not used[nextv]): rdfs(nextv,k)

for i in range(maxv):
    if not used[i] : dfs(i)

used = [0 for i in range(maxv)]
k=0
for i in reversed(vs):
    if not used[i] : rdfs(i,k)
    k += 1

q = int(input())

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