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



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

output:
1
0
1
1
"""

import sys

sys.setrecursionlimit(int(1e5))


def generate_adj_table(_v_info):
    for v_detail in _v_info:
        v_from, v_to = map(int, v_detail)
        init_adj_table[v_from].append(v_to)
    return init_adj_table


def Tarjan(current, low, dfn, scc_stack, in_scc_stack):
    global timer
    dfn[current] = low[current] = timer
    timer += 1

    scc_stack.append(current)
    in_scc_stack[current] = True

    current_scc_set = set()
    for adj in adj_table[current]:
        if not dfn[adj]:
            Tarjan(adj, low, dfn, scc_stack, in_scc_stack)
            low[current] = min(low[current], low[adj])

        elif in_scc_stack[adj]:
            low[current] = min(low[current], dfn[adj])

    scc_candidate = -1
    if dfn[current] == low[current]:
        while scc_candidate != current:
            scc_candidate = scc_stack.pop()
            in_scc_stack[scc_candidate] = False
            current_scc_set.add(scc_candidate)

        init_scc_sets_list.append(current_scc_set)

    return None


def scc_cluster():
    dfn = [0] * vertices
    low = [0] * vertices
    scc_stack = list()
    in_scc_stack = [False] * vertices

    for v in range(vertices):
        if not dfn[v]:
            Tarjan(v, low, dfn, scc_stack, in_scc_stack)

    return init_scc_sets_list


def solve(_scc_sets_list):
    for question in q_list:
        flag = False
        ele1, ele2 = map(int, question)
        for each in _scc_sets_list:
            if (ele1 in each) and (ele2 in each):
                flag = True
                break
        if flag:
            print('1')
        else:
            print('0')

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:edges + 1])
    q_num = int(_input[edges + 1])
    q_list = map(lambda x: x.split(), _input[edges + 2:])

    init_adj_table = tuple([] for _ in range(vertices))
    adj_table = generate_adj_table(v_info)

    timer = 0
    init_scc_sets_list = []
    scc_sets_list = scc_cluster()

    solve(scc_sets_list)

Solution (Python):



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

output:
1
0
1
1
"""

import sys

sys.setrecursionlimit(int(1e5))


def generate_adj_table(_v_info):
    for v_detail in _v_info:
        v_from, v_to = map(int, v_detail)
        init_adj_table[v_from].append(v_to)
    return init_adj_table


def Tarjan(current, low, dfn, scc_stack, in_scc_stack):
    global timer
    timer += 1
    dfn[current] = low[current] = timer

    scc_stack.append(current)
    in_scc_stack[current] = True

    current_scc_set = set()
    for adj in adj_table[current]:
        if not dfn[adj]:
            Tarjan(adj, low, dfn, scc_stack, in_scc_stack)
            low[current] = min(low[current], low[adj])

        elif in_scc_stack[adj]:
            low[current] = min(low[current], dfn[adj])

    scc_candidate = -1
    if dfn[current] == low[current]:
        while scc_candidate != current:
            scc_candidate = scc_stack.pop()
            in_scc_stack[scc_candidate] = False
            current_scc_set.add(scc_candidate)

        init_scc_sets_list.append(current_scc_set)

    return None


def scc_cluster():
    dfn = [0] * vertices
    low = [0] * vertices
    scc_stack = list()
    in_scc_stack = [False] * vertices

    for v in range(vertices):
        if not dfn[v]:
            Tarjan(v, low, dfn, scc_stack, in_scc_stack)

    return init_scc_sets_list


def solve(_scc_sets_list):
    for question in q_list:
        flag = False
        ele1, ele2 = map(int, question)
        for each in _scc_sets_list:
            if (ele1 in each) and (ele2 in each):
                flag = True
                break
        if flag:
            print('1')
        else:
            print('0')

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:edges + 1])
    q_num = int(_input[edges + 1])
    q_list = map(lambda x: x.split(), _input[edges + 2:])

    init_adj_table = tuple([] for _ in range(vertices))
    adj_table = generate_adj_table(v_info)

    timer = 0
    init_scc_sets_list = []
    scc_sets_list = scc_cluster()

    solve(scc_sets_list)

Solution (Python):



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

output:
1
0
1
1
"""

import sys

sys.setrecursionlimit(int(1e5))


def generate_adj_table(_v_info):
    for v_detail in _v_info:
        v_from, v_to = map(int, v_detail)
        init_adj_table[v_from].append(v_to)
    return init_adj_table


def Tarjan(current, low, dfn, scc_stack, in_scc_stack):
    global timer
    dfn[current] = low[current] = timer
    timer += 1

    scc_stack.append(current)
    in_scc_stack[current] = True

    current_scc_set = set()
    for adj in adj_table[current]:
        
        if dfn[adj] == -1:
            Tarjan(adj, low, dfn, scc_stack, in_scc_stack)
            low[current] = min(low[current], low[adj])
        
        elif in_scc_stack[adj]:
            low[current] = min(low[current], dfn[adj])

    scc_candidate = -1
    if dfn[current] == low[current]:
        while scc_candidate != current:
            scc_candidate = scc_stack.pop()
            in_scc_stack[scc_candidate] = False
            current_scc_set.add(scc_candidate)

        init_scc_sets_list.append(current_scc_set)

    return None


def scc_cluster():
    dfn = [-1] * vertices
    low = [-1] * vertices
    scc_stack = list()
    in_scc_stack = [False] * vertices

    for v in range(vertices):
        if dfn[v] == -1:
            Tarjan(v, low, dfn, scc_stack, in_scc_stack)

    return init_scc_sets_list


def solve(_scc_sets_list):
    for question in q_list:
        flag = False
        ele1, ele2 = map(int, question)
        for each in _scc_sets_list:
            if (ele1 in each) and (ele2 in each):
                flag = True
                break
        if flag:
            print('1')
        else:
            print('0')

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:edges + 1])
    q_num = int(_input[edges + 1])
    q_list = map(lambda x: x.split(), _input[edges + 2:])

    init_adj_table = tuple([] for _ in range(vertices))
    adj_table = generate_adj_table(v_info)

    timer = 0
    init_scc_sets_list = []
    scc_sets_list = scc_cluster()

    solve(scc_sets_list)

Solution (Python):

import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

adj = [[] for i in range(V)]

for i in range(E):
    s, t = map(int, file_input.readline().split())
    adj[s].append(t)



import collections

sys.setrecursionlimit(100000)

S = collections.deque()
indices = [None] * V
lowlink = [None] * V
onStack = [False] * V
index = 0
scc_id = [None] * V

def strong_connect(v):
    global index
    indices[v] = index
    lowlink[v] = index
    index += 1
    S.append(v)
    onStack[v] = True

    for w in adj[v]:
        if indices[w] == None:
            strong_connect(w)
            lowlink[v] = min(lowlink[v], lowlink[w])
        elif onStack[w]:
            lowlink[v] = min(lowlink[v], indices[w])

    if lowlink[v] == indices[v]:
        while S:
            w = S.pop()
            onStack[w] = False
            scc_id[w] = v
            if w == v:
                break

for v in range(V):
    if not indices[v]:
        strong_connect(v)



Q = file_input.readline()

for line in file_input:
    u, v = map(int, line.split())
    if scc_id[u] == scc_id[v]:
        print(1)
    else:
        print(0)

Solution (Python):


 
"""
input:
5 6
0 1
1 0
1 2
2 4
4 3
3 2
4
0 1
0 3
2 3
3 4
 
output:
1
0
1
1
"""
 
import sys
from math import isinf
 
sys.setrecursionlimit(int(1e5))
 
 
def generate_adj_table(_v_info):
    for v_detail in _v_info:
        v_from, v_to = map(int, v_detail)
        init_adj_table[v_from].append(v_to)
    return init_adj_table
 
 
def Tarjan(current, low, dfn, scc_stack, in_scc_stack):
    global timer
    dfn[current] = low[current] = timer
    timer += 1
 
    scc_stack.append(current)
    in_scc_stack[current] = True
 
    current_scc_set = set()
    for adj in adj_table[current]:
        if isinf(dfn[adj]):
            Tarjan(adj, low, dfn, scc_stack, in_scc_stack)
            low[current] = min(low[current], low[adj])
 
        elif in_scc_stack[adj]:
            low[current] = min(low[current], dfn[adj])
 
    scc_candidate = -1
    if dfn[current] == low[current]:
        while scc_candidate != current:
            scc_candidate = scc_stack.pop()
            in_scc_stack[scc_candidate] = False
            current_scc_set.add(scc_candidate)
 
        init_scc_sets_list.append(current_scc_set)
 
    return None
 
 
def scc_cluster():
    dfn = [float('inf')] * vertices
    low = [float('inf')] * vertices
    scc_stack = list()
    in_scc_stack = [False] * vertices
 
    for v in range(vertices):
        if isinf(dfn[v]):
            Tarjan(v, low, dfn, scc_stack, in_scc_stack)
 
    return init_scc_sets_list
 
 
def solve(_scc_sets_list):
    for question in q_list:
        flag = False
        ele1, ele2 = map(int, question)
        for each in _scc_sets_list:
            if (ele1 in each) and (ele2 in each):
                flag = True
                break
        if flag:
            print('1')
        else:
            print('0')
 
    return None
 
 
if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:edges + 1])
    q_num = int(_input[edges + 1])
    q_list = map(lambda x: x.split(), _input[edges + 2:])
 
    init_adj_table = tuple([] for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
 
    timer = 0
    init_scc_sets_list = []
    scc_sets_list = scc_cluster()
 
    solve(scc_sets_list)

Solution (Python):

import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

adj = [[] for i in range(V)]

for i in range(E):
    s, t = map(int, file_input.readline().split())
    adj[s].append(t)


import collections

S = collections.deque()
path = collections.deque()
index = 0
indices = [None] * V
lowlink = [None] * V
onStack = [False] * V
scc_id = [None] * V
parent = [0] * V

for v in range(V):
    if not indices[v]:
        index += 1
        indices[v] = index
        lowlink[v] = index
        S.append(v)
        path.append(v)
        onStack[v] = True

        while path:
            s = path[-1]
            adj_v = adj[s]
            for t in adj_v:
                if not indices[t]:
                    parent[t] = s
                    path.append(t)
                    S.append(t)
                    index += 1
                    indices[t] = index
                    lowlink[t] = index
                    onStack[t] = True
                    break
            if s == path[-1]:
                for t in adj_v:
                    if onStack[t]:
                        lowlink[s] = min(lowlink[s], lowlink[t])
                p = parent[s]
                lowlink[p] = min(lowlink[p], lowlink[s])
                if indices[s] == lowlink[s]:
                    while S:
                        w = S.pop()
                        onStack[w] =False
                        scc_id[w] = s
                        if w == s:
                            break
                path.pop()



Q = file_input.readline()

for line in file_input:
    u, v = map(int, line.split())
    if scc_id[u] == scc_id[v]:
        print(1)
    else:
        print(0)

Solution (Python):

import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

adj = [[] for i in range(V)]

for i in range(E):
    s, t = map(int, file_input.readline().split())
    adj[s].append(t)


import collections

S = collections.deque()
path = collections.deque()
index = 0
indices = [None] * V
lowlink = [None] * V
onStack = [False] * V
scc_id = [None] * V
parent = [0] * V

for v in range(V):
    if not indices[v]:
        index += 1
        indices[v] = index
        lowlink[v] = index
        S.append(v)
        path.append(v)
        onStack[v] = True

        while path:
            s = path[-1]
            adj_v = adj[s]
            for t in adj_v:
                if not indices[t]:
                    parent[t] = s
                    path.append(t)
                    S.append(t)
                    index += 1
                    indices[t] = index
                    lowlink[t] = index
                    onStack[t] = True
                    adj_v.remove(t)
                    break
            if s == path[-1]:
                for t in adj_v:
                    if onStack[t]:
                        lowlink[s] = min(lowlink[s], lowlink[t])
                p = parent[s]
                lowlink[p] = min(lowlink[p], lowlink[s])
                if indices[s] == lowlink[s]:
                    while S:
                        w = S.pop()
                        onStack[w] =False
                        scc_id[w] = s
                        if w == s:
                            break
                path.pop()



Q = file_input.readline()

for line in file_input:
    u, v = map(int, line.split())
    if scc_id[u] == scc_id[v]:
        print(1)
    else:
        print(0)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

def add_edge(frm,to):
    g[frm].append(to)
    rg[to].append(frm)

def dfs(now,used,back_track):
    used[now]=True
    for nx in g[now]:
        if not used[nx]:dfs(nx,used,back_track)
    back_track.append(now)

def rdfs(now,num_cmp,used,cmp):
    used[now]=True
    cmp[now]=num_cmp
    for nx in rg[now]:
        if not used[nx]:rdfs(nx,num_cmp,used,cmp)

def scc(n):
    used=[False]*n
    back_track=[]
    cmp=[-1]*n
    for v in xrange(n):
        if not used[v]:dfs(v,used,back_track)
    used=[False]*n
    num_cmp=0
    for v in back_track[::-1]:
        if not used[v]:
            rdfs(v,num_cmp,used,cmp)
            num_cmp+=1
    return num_cmp,cmp

n,m=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
rg=[[] for _ in xrange(n)]

for i in xrange(m):
    s,t=map(int,raw_input().split())
    add_edge(s,t)

num,cmp=scc(n)
q=int(raw_input())
for i in xrange(q):
    u,v=map(int,raw_input().split())
    if cmp[u]==cmp[v]:
        print(1)
    else:
        print(0)

Solution (Python):
import sys
sys.setrecursionlimit(10001)

def dfs(u, g, stack):
    visited[u] = True
    for v in g[u]:
        if not visited[v]:
            dfs(v, g, stack)
    stack.append(u)
    return stack

nv, ne = map(int, input().split(' '))
adj, tps = ([[] for _ in range(nv)] for _ in range(2))

for _ in range(ne):
    s, t = map(int, input().split(' '))
    adj[s].append(t)
    tps[t].append(s)

visited = [False] * nv
stack = []
for i in range(nv):
    if not visited[i]:
        stack = dfs(i, adj, stack)

visited = [False] * nv
comp_is = {}
while stack:
    i = stack.pop()
    if not visited[i]:
        comp = dfs(i, tps, [])
        for v in comp:
            comp_is[v] = i

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

Solution (Python):
import sys
sys.setrecursionlimit(100000)

V,E = map(int, input().split())

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

stuck = []
color = [0 for _ in range(V)]
def dfs1(s):
    color[s] = 1
    for next in D1[s]:
        if color[next] == 0:
            dfs1(next)
    stuck.append(s)
    return

for i in range(V):
    if color[i] == 0:
        dfs1(i)

color = [0 for _ in range(V)]
def dfs2(s, cnt):
    color[s] = cnt
    for next in D2[s]:
        if color[next] == 0:
            dfs2(next, cnt)
    return

stuck = stuck[::-1]
cnt = 0
for i in stuck:
    if color[i] == 0:
        cnt += 1
        dfs2(i, cnt)

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

Solution (Python):
import sys


def main():
    sys.setrecursionlimit(int(1e5))
    nvertices, nedges = map(int, input().split())
    Adj = [[] for i in range(nvertices)]
    Adjrev = [[] for i in range(nvertices)]
    for i in range(nedges):
        s, t = map(int, input().split())
        Adj[s].append(t)
        Adjrev[t].append(s)

    ordering = []
    visited = [False] * nvertices
    for u in range(nvertices):
        if not visited[u]:
            dfs1(u, Adj, visited, ordering)

    ordering.reverse()
    component_ids = [-1] * nvertices
    id = 0
    visited = [False] * nvertices
    for u in ordering:
        if visited[u]:
            continue
        dfs2(u, Adjrev, id, visited, component_ids)
        id += 1

    Q = int(input())
    for i in range(Q):
        s, t = map(int, input().split())
        if component_ids[s] == component_ids[t]:
            print(1)
        else:
            print(0)


def dfs1(u, Adj, visited, ordering):
    visited[u] = True
    for v in Adj[u]:
        if visited[v]:
            continue
        dfs1(v, Adj, visited, ordering)
    ordering.append(u)


def dfs2(u, Adj, id, visited, component_ids):
    visited[u] = True
    component_ids[u] = id
    for v in Adj[u]:
        if not visited[v]:
            dfs2(v, Adj, id, visited, component_ids)


main()

Solution (Python):
import sys

def main():
    sys.setrecursionlimit(int(1e5))
    nvertices, nedges = map(int, input().split())
    Adj = [[] for i in range(nvertices)]
    AdjRev = [[] for i in range(nvertices)]
    for i in range(nedges):
        u, v = map(int, input().split())
        Adj[u].append(v)
        AdjRev[v].append(u)

    lst = []
    visited = [False] * nvertices
    for u in range(nvertices):
        if not visited[u]:
            dfs_first(u, Adj, visited, lst)

    lst.reverse()
    ids = [-1] * nvertices
    visited = [False] * nvertices
    id = 0
    for u in lst:
        if not visited[u]:
            dfs_second(u, AdjRev, visited, id, ids)
            id += 1

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


def dfs_first(u, Adj, visited, lst):
    visited[u] = True
    for v in Adj[u]:
        if not visited[v]:
            dfs_first(v, Adj, visited, lst)
    lst.append(u)


def dfs_second(u, Adj, visited, id, ids):
    ids[u] = id
    visited[u] = True
    for v in Adj[u]:
        if not visited[v]:
            dfs_second(v, Adj, visited, id, ids)

main()

Solution (Python):
def solve():
    N, M = map(int, input().split())
    edges = [[] for _ in [0]*N]
    r_edges = [[] for _ in [0]*N]

    for _ in [0]*M:
        a, b = map(int, input().split())
        edges[a].append(b)
        r_edges[b].append(a)
        
    c = get_strongly_connected_components(edges, r_edges)
    group = [0]*N
    for i in range(len(c)):
        for v in c[i]:
            group[v] = i

    result = []
    append = result.append
    for _ in [0]*int(input()):
        a, b = map(int, input().split())
        append("1" if group[a] == group[b] else "0")

    print("\n".join(result))


def get_strongly_connected_components(edges, r_edges):
    import sys
    sys.setrecursionlimit(10**7)
    v_count = len(edges)
    order = [0]*v_count
    k = 1

    def get_order(v):
        order[v] = 1
        nonlocal k
        for dest in edges[v]:
            if order[dest] == 0:
                get_order(dest)
        order[v] = k
        k += 1

    def get_components(v):
        order[v] = 0
        return [v] + [_v for dest in r_edges[v] if order[dest] > 0 for _v in get_components(dest)]

    [None for v in range(v_count) if order[v] == 0 and get_order(v)]
    return [get_components(v) for v, _ in sorted(enumerate(order), key=lambda x: x[1], reverse=True) if order[v] > 0]

if __name__ == "__main__":
    solve()

Solution (Python):
def solve():
    N, M = map(int, input().split())
    edges = [[] for _ in [0]*N]
    r_edges = [[] for _ in [0]*N]

    for _ in [0]*M:
        a, b = map(int, input().split())
        edges[a].append(b)
        r_edges[b].append(a)

    c = get_strongly_connected_components(edges, r_edges)
    group = [0]*N
    for i in range(len(c)):
        for v in c[i]:
            group[v] = i

    result = []
    append = result.append
    for _ in [0]*int(input()):
        a, b = map(int, input().split())
        append("1" if group[a] == group[b] else "0")

    print("\n".join(result))


def get_strongly_connected_components(edges, r_edges):
    import sys
    sys.setrecursionlimit(10**7)
    v_count = len(edges)
    order = [0]*v_count
    k = [1]

    def get_order(v):
        order[v] = 1
        for dest in edges[v]:
            if order[dest] == 0:
                get_order(dest)
        order[v] = k[0]
        k[0] += 1

    def get_components(v):
        order[v] = 0
        return [v] + [_v for dest in r_edges[v] if order[dest] > 0 for _v in get_components(dest)]

    [None for v in range(v_count) if order[v] == 0 and get_order(v)]
    return [get_components(v) for v, _ in sorted(enumerate(order), key=lambda x: x[1], reverse=True) if order[v] > 0]

if __name__ == "__main__":
    solve()

Solution (Python):
def solve():
    N, M = map(int, input().split())
    edges = [[] for _ in [0]*N]
    r_edges = [[] for _ in [0]*N]

    for _ in [0]*M:
        a, b = map(int, input().split())
        edges[a].append(b)
        r_edges[b].append(a)

    c = get_strongly_connected_components(edges, r_edges)
    group = [0]*N
    for i in range(len(c)):
        for v in c[i]:
            group[v] = i

    result = []
    append = result.append
    for _ in [0]*int(input()):
        a, b = map(int, input().split())
        append("1" if group[a] == group[b] else "0")

    print("\n".join(result))


def get_strongly_connected_components(edges, r_edges):
    import sys
    sys.setrecursionlimit(10**7)
    v_count = len(edges)
    order = [0]*v_count
    k = [1]

    def get_order(v):
        order[v] = 1
        [None for dest in edges[v] if order[dest] == 0 and get_order(dest)]
        order[v] = k[0]
        k[0] += 1

    def get_components(v):
        order[v] = 0
        return [v] + [_v for dest in r_edges[v] if order[dest] > 0 for _v in get_components(dest)]

    [None for v in range(v_count) if order[v] == 0 and get_order(v)]
    return [get_components(v) for v, _ in sorted(enumerate(order), key=lambda x: x[1], reverse=True) if order[v] > 0]

if __name__ == "__main__":
    solve()

Solution (Python):
def solve():
    N, M = map(int, input().split())
    edges = [[] for _ in [0]*N]
    r_edges = [[] for _ in [0]*N]

    for _ in [0]*M:
        a, b = map(int, input().split())
        edges[a].append(b)
        r_edges[b].append(a)

    c = kosaraju(edges, r_edges)
    group = [0]*N
    for i in range(len(c)):
        for v in c[i]:
            group[v] = i

    result = []
    append = result.append
    for _ in [0]*int(input()):
        a, b = map(int, input().split())
        append("1" if group[a] == group[b] else "0")

    print("\n".join(result))


def kosaraju(edges, reverse_edges):
    import sys
    sys.setrecursionlimit(10**7)
    v_count = len(edges)
    order = [0]*v_count
    k = [1]

    def get_order(v):
        order[v] = 1
        for dest in filter(lambda x: order[x] == 0, edges[v]):
            get_order(dest)
        order[v] = k[0]
        k[0] += 1

    def get_components(v):
        order[v] = 0
        return [v] + [_v for dest in reverse_edges[v] if order[dest] > 0 for _v in get_components(dest)]

    for v in filter(lambda x: order[x] == 0, range(v_count)):
        get_order(v)
    return [get_components(v) for v, _ in sorted(enumerate(order), key=lambda x: x[1], reverse=True) if order[v] > 0]

if __name__ == "__main__":
    solve()

Solution (Python):
def solve():
    N, M = map(int, input().split())
    edges = [[] for _ in [0]*N]
    r_edges = [[] for _ in [0]*N]

    for _ in [0]*M:
        a, b = map(int, input().split())
        edges[a].append(b)
        r_edges[b].append(a)

    c = kosaraju(edges, r_edges)
    group = [0]*N
    for i in range(len(c)):
        for v in c[i]:
            group[v] = i

    result = []
    append = result.append
    for _ in [0]*int(input()):
        a, b = map(int, input().split())
        append("1" if group[a] == group[b] else "0")

    print("\n".join(result))


def kosaraju(edges, reverse_edges):
    import sys
    sys.setrecursionlimit(10**7)
    v_count = len(edges)
    order = [0]*v_count
    k = [1]

    def get_order(v):
        order[v] = 1
        for dest in (_v for _v in edges[v] if order[_v] == 0):
            get_order(dest)
        order[v] = k[0]
        k[0] += 1

    def get_components(v):
        order[v] = 0
        return [v] + [_v for dest in reverse_edges[v] if order[dest] > 0 for _v in get_components(dest)]

    for v in (_v for _v in range(v_count) if order[_v] == 0):
        get_order(v)
    return [get_components(v) for v, _ in sorted(enumerate(order), key=lambda x: x[1], reverse=True) if order[v] > 0]

if __name__ == "__main__":
    solve()

Solution (Python):
def solve():
    N, M = map(int, input().split())
    edges = [[] for _ in [0]*N]
    r_edges = [[] for _ in [0]*N]

    for _ in [0]*M:
        a, b = map(int, input().split())
        edges[a].append(b)
        r_edges[b].append(a)

    c = kosaraju(edges, r_edges)
    group = [0]*N
    for i in range(len(c)):
        for v in c[i]:
            group[v] = i

    result = []
    append = result.append
    for _ in [0]*int(input()):
        a, b = map(int, input().split())
        append("1" if group[a] == group[b] else "0")

    print("\n".join(result))


def kosaraju(edges, reverse_edges):
    import sys
    sys.setrecursionlimit(10**7)
    v_count = len(edges)
    order = [0]*v_count
    k = [1]

    def get_order(v):
        order[v] = 1
        [None for dest in edges[v] if order[dest] == 0 and get_order(dest)]
        order[v] = k[0]
        k[0] += 1

    def get_components(v):
        order[v] = 0
        return [v] + [_v for dest in reverse_edges[v] if order[dest] > 0 for _v in get_components(dest)]

    [None for v in range(v_count) if order[v] == 0 and get_order(v)]
    return [get_components(v) for v, _ in sorted(enumerate(order), key=lambda x: x[1], reverse=True) if order[v] > 0]

if __name__ == "__main__":
    solve()

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

def counter():
    cnt = 0
    while True:
        yield cnt
        cnt += 1

def dfs(here, visited, track, count, connect):
    visited |= {here}
    for c in connect[here]:
        if c not in visited:
            dfs(c, visited, track, count, connect)
    track[here] = next(count)

def kosaraju(here, visited, track, count, connect):
    visited |= {here}
    for c in connect[here]:
        if c not in visited:
            kosaraju(c, visited, track, count, connect)
    track[here] = count

vertices, edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
reversed_connect = defaultdict(list)
for _ in range(edges):
    v1, v2 = (int(n) for n in input().split(" "))
    connect[v1].append(v2)
    reversed_connect[v2].append(v1)

visited = set()
track_gen = counter()
track = [-1 for n in range(vertices)]
for v in range(vertices):
    if v not in visited:
        dfs(v, visited, track, track_gen, connect)

visited = set()
track_gen = counter()
strongly_con = [-1 for n in range(vertices)]
for v in range(vertices - 1 ,- 1, -1):
    here = track.index(v)
    if here not in visited:
        num = next(track_gen)
        kosaraju(here, visited, strongly_con, num, reversed_connect)

q_num = int(input())
for _ in range(q_num):
    v1, v2 = (int(n) for n in input().split(" "))
    if strongly_con[v1] == strongly_con[v2]:
        print(1)
    else:
        print(0)

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

def counter():
    cnt = 0
    while True:
        yield cnt
        cnt += 1

def dfs(here, visited, track, count, connect):
    visited |= {here}
    for c in connect[here]:
        if c not in visited:
            dfs(c, visited, track, count, connect)
    track.append(here)

def kosaraju(here, visited, track, count, connect):
    visited |= {here}
    for c in connect[here]:
        if c not in visited:
            kosaraju(c, visited, track, count, connect)
    track[here] = count

vertices, edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
reversed_connect = defaultdict(list)
for _ in range(edges):
    v1, v2 = (int(n) for n in input().split(" "))
    connect[v1].append(v2)
    reversed_connect[v2].append(v1)

visited = set()
track_gen = counter()
track = []
for v in range(vertices):
    if v not in visited:
        dfs(v, visited, track, track_gen, connect)

visited = set()
track_gen = counter()
strongly_con = [-1 for n in range(vertices)]
for here in track[::-1]:
    if here not in visited:
        num = next(track_gen)
        kosaraju(here, visited, strongly_con, num, reversed_connect)

q_num = int(input())
for _ in range(q_num):
    v1, v2 = (int(n) for n in input().split(" "))
    if strongly_con[v1] == strongly_con[v2]:
        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):
  visited[v] = True
  for to in reverse_edges[v]:
    if not visited[to]:
      parent[to] = v
      search_strongly_connection(to, visited, reverse_edges, parent)

def find(parent, x):
  if parent[x] == x:
    return x
  tmp = find(parent, parent[x])
  parent[x] = tmp
  return tmp

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)

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