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

    # Go through all vertices adjacent to this
    for adj in adj_table[current]:

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

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

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

        elif stack_member[adj]:

            '''Update low value of 'current' only if 'adj' 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[current] = min(low[current], disc[adj])

    # head node found, pop the stack and print an SCC
    scc_candidate = -1  # To store stack extracted vertices
    if low[current] == disc[current]:
        while scc_candidate != current:
            scc_candidate = st.pop()
            scc_set.add(scc_candidate)
            stack_member[scc_candidate] = 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
                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)

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

Submission status: Accepted

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

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

    current_scc_set = set()
    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()
            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, 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()
    solve()

Submission status: Accepted

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

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

    current_scc_set = set()
    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()
            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, 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 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()
    solve()

Submission status: Accepted

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)

    current_scc_set = set()
    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()
            current_scc_set.add(scc_candidate)
            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
    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 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 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()
    solve()

Submission status: Accepted

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

Submission status: Accepted

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, 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(low[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(low[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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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(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]:
        # adj unvisited
        if dfn[adj] == -1:
            Tarjan(adj, low, dfn, scc_stack, in_scc_stack)
            low[current] = min(low[current], low[adj])
        # current -> adj: by back-edge or cross-edge
        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)

Submission status: Accepted

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


# 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: Accepted

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

Submission status: Accepted

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


# 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: Accepted

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

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

Submission status: Accepted

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