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: Wrong Answer

Solution code:
#!/usr/bin/env python3
# GRL_3_C: Connected Components - Strongly Connected Components


from collections import namedtuple


DirectedEdge = namedtuple('DirectedEdge', ('src', 'dest'))


def revert(edge):
    return edge._replace(src=edge.dest, dest=edge.src)


class Digraph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, edge):
        self._edges[edge.src].append(edge)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e

    def reversed(self):
        g = self.__class__(self.v)
        for e in self.edges():
            g.add(revert(e))

        return g


def reverse_post(graph):
    def visit(e):
        if not visited[e.dest]:
            visited[e.dest] = True
            return True
        else:
            return False

    def leave(e):
        vs.append(e.src)
        return False

    visited = [False] * graph.v
    vs = []

    for i in range(graph.v):
        if not visited[i]:
            stack = [(e, visit) for e in graph.adj(i)]
            while stack:
                e, f = stack.pop()
                if f(e):
                    stack.append((e, leave))
                    for ne in graph.adj(e.dest):
                        stack.append((e, visit))
    return reversed(vs)


def scc_kosaraju_sharir(graph):
    class CC:
        def __init__(self, v):
            self._id = [i for i in range(v)]

        def id(self, v, c):
            self._id[v] = c

        def connected(self, u, v):
            return self._id[u] == self._id[v]

    def dfs(v):
        stack = [v]
        while stack:
            w = stack.pop()
            if not visited[w]:
                visited[w] = True
                yield w
                stack.extend([e.dest for e in graph.adj(w)
                              if not visited[e.dest]])

    visited = [False] * graph.v
    i = 0
    cc = CC(graph.v)
    for v in reverse_post(graph.reversed()):
        if not visited[v]:
            for w in dfs(v):
                cc.id(w, i)
            i += 1
    return cc


def run():
    v, e = [int(i) for i in input().split()]
    g = Digraph(v)

    for _ in range(e):
        s, t = [int(i) for i in input().split()]
        g.add(DirectedEdge(s, t))

    cc = scc_kosaraju_sharir(g)
    q = int(input())
    for _ in range(q):
        u, w = [int(i) for i in input().split()]
        if cc.connected(u, w):
            print(1)
        else:
            print(0)


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

N,M=MAP()
nodes1=[[] for i in range(N)]
nodes2=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes1[u].append(v)
    nodes2[v].append(u)

T=[]
visited=[False]*N
def rec1(cur):
    visited[cur]=True
    for nxt in nodes1[cur]:
        if not visited[nxt]:
            rec1(nxt)
    # 行き止まったところから順にTに入れていく
    T.append(cur)

rec1(0)

visited=[False]*N
group=[0]*N
grpnum=1
def rec2(cur):
    global grpnum
    group[cur]=grpnum
    visited[cur]=True
    for nxt in nodes2[cur]:
        if not visited[nxt]:
            rec2(nxt)
            return
    grpnum+=1
    return

# 逆順で進めるところまで行く
for u in reversed(T):
    if not visited[u]:
        rec2(u)

Q=INT()
for _ in range(Q):
    u,v=MAP()
    if group[u]==group[v]:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

N,M=MAP()
nodes1=[[] for i in range(N)]
nodes2=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes1[u].append(v)
    nodes2[v].append(u)

T=[]
visited=[False]*N
def rec1(cur):
    visited[cur]=True
    for nxt in nodes1[cur]:
        if not visited[nxt]:
            rec1(nxt)
    # 行き止まったところから順にTに入れていく
    T.append(cur)

# グラフが連結とは限らないので全頂点やる
for u in range(N):
    if not visited[u]:
        rec1(u)

visited=[False]*N
group=[0]*N
grpnum=1
def rec2(cur):
    global grpnum
    group[cur]=grpnum
    visited[cur]=True
    for nxt in nodes2[cur]:
        if not visited[nxt]:
            rec2(nxt)
            return
    grpnum+=1
    return

# 逆順で進めるところまで行く
for u in reversed(T):
    if not visited[u]:
        rec2(u)

Q=INT()
for _ in range(Q):
    u,v=MAP()
    if group[u]==group[v]:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def search(g, v):
    visited = set()
    lowest = [None] * v
    parent = [None] * v
    prenum = [None] * v
    child = defaultdict(list)

    for i in range(v):
        if i in visited:
            continue
        root = i

        # dfs??§tree?????????
        stack = [(root, None)]
        while stack:
            u, prev = stack.pop()
            if u not in visited:
                parent[u] = prev
                if prev is not None:
                    child[prev].append(u)
                visited |= {u}
                prenum[u] = lowest[u] = len(visited)

            stack.extend([(v, u) for v in g[u][::-1] if v not in visited])    

    # lowest????¨????
    from collections import Counter
    leaf = [i for i in range(v) if not child[i]]
    unfinished = Counter()
    for li in leaf:
        while li is not None:
            # candidate = [prenum[li]] + [prenum[i] for i in g[li] if i != parent[li]] + [lowest[i] for i in child[li]] #???undirected
            candidate = [prenum[li]] + [prenum[i] for i in g[li]] + [lowest[i] for i in child[li]] # directed
            lowest[li] = min(candidate)
            li = parent[li]
            if li is not None and 1 < len(child[li]):
                unfinished[li] += 1
                if unfinished[li] < len(child[li]):
                    break
    return prenum, lowest

from sys import stdin
readline = stdin.readline


def main():
    v, e = map(int, readline().split())
    from collections import defaultdict
    g = defaultdict(list)

    for _ in range(e):
        s, t = map(int, readline().split())
        g[s].append(t)
    
    prenum, lowest = search(g, v)
    q = int(readline())
    for u, v in [map(int, readline().split()) for _ in range(q)]:
        print(1 if lowest[u] == lowest[v] else 0)
main()

Submission status: Wrong Answer

Solution code:
from collections import UserList
class Stack(UserList):
    def __init__(self):
        UserList.__init__(self)
        self.contains = set()
    def __contains__(self, x):
        return x in self.contains
    def __and__(self, x):
        return self.contains & x
    def push(self, x):
        if x in self.contains:
            return
        self.data.append(x)
        self.contains |= {x}
    def pop(self):
        x = self.data.pop()
        self.contains -= {x}
        return x

from collections import defaultdict
from collections import Counter
def search(g, v):
    visited = set()
    lowest = [None] * v
    parent = [None] * v
    prenum = [None] * v
    child = defaultdict(list)
    backtrack = defaultdict(set)

    for root in range(v):
        if root in visited:
            continue

        route = Stack()
        route.push(None)
        dfs_stack = [(root, route[-1])]
        while dfs_stack:
            u, prev = dfs_stack.pop()
            if u in visited:
                continue

            parent[u] = prev
            if prev is not None:
                child[prev].append(u)
            visited |= {u}
            prenum[u] = lowest[u] = len(visited)

            while route[-1] != prev:
                route.pop()
            backtrack[u] = route & g[u]
            route.push(u)
            
            dfs_stack.extend((v, u) for v in g[u] - visited) 

        from heapq import heappush, heappop
        heap = []
        for i in range(v):
            if backtrack[i]:
                heappush(heap, (prenum[i], i))
        while heap:
            _, i = heappop(heap)
            low, bi = min((lowest[bi], bi) for bi in backtrack[i])
            while i != bi:
                lowest[i] = low
                i = parent[i]
    return prenum, lowest

from sys import stdin
readline = stdin.readline

def main():
    v, e = map(int, readline().split())
    from collections import defaultdict
    g = defaultdict(set)

    for _ in range(e):
        s, t = map(int, readline().split())
        g[s] |= {t}        
    
    prenum, lowest = search(g, v)
    q = int(readline())
    for u, v in [map(int, readline().split()) for _ in range(q)]:
        print(1 if lowest[u] == lowest[v] else 0)
    
main()

Submission status: Wrong Answer

Solution code:
def search(g, g_dash, v):
    # search prenum
    visited = set()
    prenum = []
    for root in range(v):
        if root in visited:
            continue
        dfs_stack = [root]
        while dfs_stack:
            u = dfs_stack.pop()
            if u in visited:
                continue
            visited |= {u}
            prenum.append(u)
            dfs_stack.extend(g[u] - visited)

    # reverse search lowest
    visited.clear()
    lowest = [None] * v
    for root in prenum:
        if root in visited:
            continue
        dfs_stack = [root]
        while dfs_stack:
            u = dfs_stack.pop()
            if u in visited:
                continue
            visited |= {u}
            lowest[u] = root
            dfs_stack.extend(g_dash[u] - visited)
    return lowest

from sys import stdin
readline = stdin.readline

def main():
    v, e = map(int, readline().split())
    from collections import defaultdict
    g = defaultdict(set)
    g_dash = defaultdict(set)
    

    for _ in range(e):
        s, t = map(int, readline().split())
        g[s] |= {t}        
        g_dash[t] |= {s}        
    
    lowest = search(g, g_dash, v)
    q = int(readline())
    for u, v in [map(int, readline().split()) for _ in range(q)]:
        print(1 if lowest[u] == lowest[v] else 0)
main()

Submission status: Wrong Answer

Solution code:
from collections import UserList
class Stack(UserList):
    def __init__(self):
        UserList.__init__(self)
        self.contains = set()
    def __contains__(self, x):
        return x in self.contains
    def __and__(self, x):
        return self.contains & x
    def push(self, x):
        if x in self.contains:
            return
        self.data.append(x)
        self.contains |= {x}
    def pop(self):
        x = self.data.pop()
        self.contains -= {x}
        return x

def search(g, v):
    # search prenum
    backtrack = defaultdict(set)
    visited = set()
    prenum = []
    for root in range(v):
        if root in visited:
            continue
        route = Stack()
        route.push(None)
        dfs_stack = [(root, None)]            
        while dfs_stack:
            u, prev = dfs_stack.pop()
            if u in visited:
                continue
            visited |= {u}
            prenum.append(u)
            dfs_stack.extend((v, u) for v in g[u] - visited)
            while route[-1] != prev:
                route.pop()
            if prev is not None:
                backtrack[u] |= {prev}
            for i in route & g[u]:
                backtrack[i] |= {u}
            route.push(u)
                
    # reverse search lowest
    visited.clear()
    lowest = [None] * v
    for root in prenum:
        if root in visited:
            continue
        dfs_stack = [root]
        while dfs_stack:
            u = dfs_stack.pop()
            if u in visited:
                continue
            visited |= {u}
            lowest[u] = root
            dfs_stack.extend(backtrack[u] - visited)
    #print(prenum)
    #print(lowest)
    return lowest

from sys import stdin
from collections import defaultdict
readline = stdin.readline

def main():
    v, e = map(int, readline().split())
    g = defaultdict(set)

    for _ in range(e):
        s, t = map(int, readline().split())
        g[s] |= {t}        
    
    lowest = search(g, v)
    q = int(readline())
    for u, v in [map(int, readline().split()) for _ in range(q)]:
        print(1 if lowest[u] == lowest[v] else 0)
main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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(1e4))


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 graph_dfs(u, low, disc, stack_member, st):
    global Time
    # Initialize discovery time and low value
    disc[u] = Time
    low[u] = Time
    Time += 1
    stack_member[u] = True
    st.append(u)
    scc_set = set()

    # Go through all vertices adjacent to this
    for v in adj_table[u]:

        # If v is not visited yet, then recur for it
        if disc[v] == -1:

            graph_dfs(v, low, disc, stack_member, st)

            # Check if the subtree rooted with v has a connection to
            # one of the ancestors of u
            # Case 1 (per above discussion on Disc and Low value)
            low[u] = min(low[u], low[v])

        elif stack_member[v]:

            '''Update low value of 'u' only if 'v' is still in stack
            (i.e. it's a back edge, not cross edge).
            Case 2 (per above discussion on Disc and Low value) '''
            low[u] = min(low[u], disc[v])

    # head node found, pop the stack and print an SCC
    w = -1  # To store stack extracted vertices
    if low[u] == disc[u]:
        while w != u:
            w = st.pop()
            scc_set.add(w)
            stack_member[w] = False
        ans.append(scc_set)

    return None


def scc():
    # Mark all the vertices as not visited
    # and Initialize parent and visited,
    # and ap(articulation point) arrays
    disc = [-1] * vertices
    low = [-1] * vertices
    stack_member = [False] * vertices
    st = []

    # Call the recursive helper function
    # to find articulation points
    # in DFS tree rooted with vertex 'i'
    for v in range(vertices):
        if disc[v] == -1:
            graph_dfs(v, low, disc, stack_member, st)

    return ans


def solve():
    for question in q_list:
        flag = False
        ele1, ele2 = map(int, question)
        for each in scc_sets:
            if (ele1 in each) and (ele2 in each):
                flag = True
        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)

    Time = 0
    ans = []
    scc_sets = scc()
    print(scc_sets)
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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, disc, scc_stack, in_scc_stack):
    global timer
    disc[current] = low[current] = timer
    timer += 1

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

    for adj in adj_table[current]:
        if isinf(disc[adj]):
            Tarjan(adj, low, disc, scc_stack, in_scc_stack)
            low[current] = min(low[current], low[adj])

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

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

    return None


def scc():
    disc = [float('inf')] * vertices
    low = [float('inf')] * vertices
    scc_stack = list()
    in_scc_stack = [False] * vertices

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

    return low


def solve():
    res = scc()
    for question in q_list:
        ele1, ele2 = map(int, question)
        if res[ele1] == res[ele2]:
            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
    solve()

Submission status: Wrong Answer

Solution code:
# Acceptance of input
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)

# Tarjan's strongly connected components algorithm(repetition)
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])
                        adj[s].remove(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()


# Output
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)

Submission status: Wrong Answer

Solution code:
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 = [[] for _ in range(nv)]
tps = [[] for _ in range(nv)]

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

visited = [False] * nv
stack = dfs(0, adj, [])
visited = [False] * nv
comps = []

while stack:
    i = stack.pop()
    if not visited[i]:
        comp = dfs(i, tps, [])
        comps.append(comp)

nv = int(input())
for _ in range(nv):
    u, v = map(int, input().split(' '))
    ans = 0

    for comp in comps:
        if u in comp and v in comp:
            ans = 1

    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

V,E = map(int, input().split())
#??£??\????????????D1??¨?????????D2???????????????
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

dfs1(0)

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)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
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)
    print(c)
    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()

Submission status: Wrong Answer

Solution code:
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 edges[_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()

Submission status: Wrong Answer

Solution code:
"""
強連結成分分解
"""


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
dfs(0, 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)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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(1e6))


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, disc, visited, scc_stack):
    global timer
    disc[current] = low[current] = timer
    timer += 1

    visited[current] = True
    scc_stack.append(current)
    current_scc_set = set()
    for adj in adj_table[current]:
        if not visited[adj]:
            Tarjan(adj, low, disc, visited, scc_stack)
            low[current] = min(low[current], low[adj])
        elif adj in scc_stack:
            low[current] = min(low[current], disc[adj])

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

        init_scc_sets_list.append(current_scc_set)

    return None


def scc():
    disc = [float('inf')] * vertices
    low = [float('inf')] * vertices
    visited = [False] * vertices
    scc_stack = []

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

    return init_scc_sets_list


def solve():
    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 scc_sets_list


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()
    res = solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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(1e6))


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, disc, visited, scc_stack, in_scc_stack):
    global timer
    disc[current] = low[current] = timer
    timer += 1

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

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

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

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

        init_scc_sets_list.append(current_scc_set)

    return None


def scc():
    disc = [float('inf')] * vertices
    low = [float('inf')] * vertices
    visited = [False] * vertices
    scc_stack = []
    in_scc_stack = [False] * vertices

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

    return init_scc_sets_list


def solve():
    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 scc_sets_list


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()
    res = solve()