Problem:


Strongly Connected Components

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

Input

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

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

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

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

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

Output

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

Constraints

1 ≤ |V| ≤ 10,000

0 ≤ |E| ≤ 30,000

1 ≤ Q ≤ 100,000

Sample Input 1

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

Sample Output 1

1
0
1
1



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


Sample output:
1
0
1
1

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Runtime Error

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

    # 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] 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: Runtime Error

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

    # 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] 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 collections import defaultdict
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: Runtime Error

Solution code:
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: Runtime Error

Solution code:
def f_dfs(i):
    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)


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(int, input().split())
    f_edges[s].add(t)
    b_edges[t].add(s)

visited = [False] * n
finish_order = [None] * n
counter = 0

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

visited = [False] * n
groups = [None] * 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())

while q:
    q -= 1
    u, v = map(int, input().split())
    print(int(groups[u] == groups[v]))

Submission status: Runtime Error

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

Submission status: Runtime Error

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(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 isinf(disc[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 = list()
    in_scc_stack = [False] * vertices

    for v in range(vertices):
        if isinf(disc[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()

Submission status: Runtime Error

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

Submission status: Runtime Error

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, 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
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: Runtime Error

Solution code:
def main():
    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)

    component_ids = [-1] * nvertices
    id = 0
    for u in range(nvertices):
        if component_ids[u] != -1:
            continue
        s1 = set()
        s2 = set()
        visited1 = [0] * nvertices
        visited2 = [0] * nvertices
        dfs(u, Adj, visited1, s1)
        dfs(u, Adjrev, visited2, s2)
        for v in s1 & s2:
            component_ids[v] = id
        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 dfs(u, Adj, visited, s):
    visited[u] = 1
    s.add(u)
    for v in Adj[u]:
        if visited[v]:
            continue
        dfs(v, Adj, visited, s)
    return s


main()

Submission status: Runtime Error

Solution code:
def main():
    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 range(Adj[u]):
        if not visited[v]:
            dfs2(v, Adj, id, visited)


main()

Submission status: Runtime Error

Solution code:
def main():
    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()

Submission status: Runtime Error

Solution code:
import sys


def main():
    sys.setrecursionlimit(int(1e4))
    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()

Submission status: Runtime Error

Solution code:
def main():
    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()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
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)

Submission status: Runtime Error

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