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

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

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

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

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

Submission status: Accepted

Solution code:
import sys


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

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

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

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


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


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


main()

Submission status: Accepted

Solution code:
import sys

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

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

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

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


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


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

main()

Submission status: Accepted

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

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

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
        for dest in edges[v]:
            if order[dest] == 0:
                get_order(dest)
        order[v] = k[0]
        k[0] += 1

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

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

if __name__ == "__main__":
    solve()

Submission status: Accepted

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
        [None for dest in edges[v] if order[dest] == 0 and get_order(dest)]
        order[v] = k[0]
        k[0] += 1

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

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

if __name__ == "__main__":
    solve()

Submission status: Accepted

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 filter(lambda x: order[x] == 0, edges[v]):
            get_order(dest)
        order[v] = k[0]
        k[0] += 1

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

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

if __name__ == "__main__":
    solve()

Submission status: Accepted

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 order[_v] == 0):
        get_order(v)
    return [get_components(v) for v, _ in sorted(enumerate(order), key=lambda x: x[1], reverse=True) if order[v] > 0]

if __name__ == "__main__":
    solve()

Submission status: Accepted

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
        [None for dest in edges[v] if order[dest] == 0 and get_order(dest)]
        order[v] = k[0]
        k[0] += 1

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

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

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

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

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

Submission status: Accepted

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

import sys

sys.setrecursionlimit(1000000)

def dfs(v, visited, edges, order):
  visited[v] = True
  for to in edges[v]:
    if not visited[to]:
      dfs(to, visited, edges, order)
  order.append(v)

def search_strongly_connection(v, visited, reverse_edges, parent):
  visited[v] = True
  for to in reverse_edges[v]:
    if not visited[to]:
      parent[to] = v
      search_strongly_connection(to, visited, reverse_edges, parent)

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

v_num , e_num = map(int, input().split())
edges = [[] for _ in range(v_num)]
reverse_edges = [[] for _ in range(v_num)]
for _ in range(e_num):
  s, t = map(int, input().split())
  edges[s].append(t)
  reverse_edges[t].append(s)


order = []
visited = [False] * v_num
for v in range(v_num):
  if not visited[v]:
    dfs(v, visited, edges, order)
order.reverse()


visited = [False] * v_num
parent = [i for i in range(v_num)]
for v in order:
  if not visited[v]:
    search_strongly_connection(v, visited, reverse_edges, parent)

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

Submission status: Accepted

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

import sys

sys.setrecursionlimit(1000000)

def dfs(v, visited, edges, order):
  visited[v] = True
  for to in edges[v]:
    if not visited[to]:
      dfs(to, visited, edges, order)
  order.append(v)

def search_strongly_connection(v, visited, reverse_edges, parent, num):
  visited[v] = True
  for to in reverse_edges[v]:
    if not visited[to]:
      parent[to] = num
      search_strongly_connection(to, visited, reverse_edges, parent, num)

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:
  num = v
  if not visited[v]:
    search_strongly_connection(v, visited, reverse_edges, parent, num)

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

Submission status: Accepted

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

import sys

sys.setrecursionlimit(1000000)

def dfs(v, visited, edges, order):
  visited[v] = True
  for to in edges[v]:
    if not visited[to]:
      dfs(to, visited, edges, order)
  order.append(v)

def search_strongly_connection(v, visited, reverse_edges, parent, num):
  visited[v] = True
  for to in reverse_edges[v]:
    if not visited[to]:
      parent[to] = num
      search_strongly_connection(to, visited, reverse_edges, parent, num)

def main():
  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, v)
  
  q_num = int(input())
  for _ in range(q_num):
    u, v = map(int, input().split())
    print(1 if parent[u] == parent[v] else 0)

main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def scc(n, e, re):

    v = [None] * n
    t = []
    def dfs(i):
        v[i] = 0
        for b in e[i]:
            if v[b] is None:
                dfs(b)
        t.append(i)

    for i in range(n):
        if v[i] is None:
            dfs(i)

    r = [None] * n
    def dfs2(i, p):
        r[i] = p
        for b in re[i]:
            if r[b] is None:
                dfs2(b, p)

    for c in t[::-1]:
        if r[c] is None:
            dfs2(c, c)

    return r

def main():
    n,m = LI()
    st = [LI() for _ in range(m)]
    q = I()
    uv = [LI() for _ in range(q)]

    e = collections.defaultdict(set)
    re = collections.defaultdict(set)
    for s,t in st:
        e[s].add(t)
        re[t].add(s)

    r = scc(n, e, re)
    rr = []
    for u,v in uv:
        if r[u] == r[v]:
            rr.append(1)
        else:
            rr.append(0)

    return JA(rr, "\n")

# start = time.time()
print(main())
# pe(time.time() - start)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a].append(b) for a, b in ab]

    def scc(g_temp):
        g, n = [set(i) for i in g_temp], len(g_temp)
        rg, cmp_, vs = [[] for _ in [0]*n], [0]*n, []
        for v1, v_list in enumerate(g):
            for v2 in v_list:
                rg[v2].append(v1)
        used = [False]*n
        for v in range(n):
            if not used[v]:
                q = [v]
                while q:
                    v = q[-1]
                    used[v] = True
                    while g[v]:
                        i = g[v].pop()
                        if not used[i]:
                            q.append(i)
                            break
                    else:
                        q.pop()
                        vs.append(v)
        used = [False]*n
        kk = [-1]
        for i in range(len(vs)-1, -1, -1):
            if not used[vs[i]]:
                q = [vs[i]]
                kk[0] += 1
                while q:
                    v, k = q[-1], kk[0]
                    used[v], cmp_[v] = True, k
                    while rg[v]:
                        i = rg[v].pop()
                        if not used[i]:
                            q.append(i)
                            break
                    else:
                        q.pop()
        k = kk[0]
        g2 = [set() for _ in [0]*(k+1)]
        for v1, v_list in enumerate(g_temp):
            for v2 in v_list:
                g2[cmp_[v1]].add(cmp_[v2])
        for v, v_set in enumerate(g2):
            if v in v_set:
                g2[v].remove(v)
        g2 = [list(v) for v in g2]
        return g2, cmp_

    s = scc(g)[1]
    q = int(input())
    for i in range(q):
        c, d = map(int, input().split())
        if s[c] == s[d]:
            print(1)
        else:
            print(0)


main()

Submission status: Accepted

Solution code:

def scc_decomposition(G):
    n = len(G)
    G_rev = [[] for _ in range(n)]
    for u in range(n):
        for v in G[u]:
            G_rev[v].append(u)

    # dfs
    vs = []
    visited = [False] * n
    used = [False] * n
    for u in range(n):
        if visited[u]:
            continue
        stack = [u]
        while stack:
            v = stack.pop()
            if used[v]:
                continue
            if not visited[v]:
                visited[v] = True
            else:
                vs.append(v)
                used[v] = True
                continue
            stack.append(v)
            for c in G[v]:
                if not visited[c]:
                    stack.append(c)

    # reverse dfs
    visited = [False] * n
    component = [-1] * n
    for i, u in enumerate(vs[::-1]):
        if visited[u]:
            continue
        stack = [u]
        while stack:
            v = stack.pop()
            visited[v] = True
            component[v] = i
            for c in G_rev[v]:
                if not visited[c]:
                    stack.append(c)

    return component

class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, x):
        r = x
        while self.parent[r] != r:
            r = self.parent[r]
        while self.parent[x] != r:
            x, self.parent[x] = self.parent[x], r
        return r

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        return self.size[self.find(x)]

V, E = map(int, input().split())
G = [[] for _ in range(V)]
for _ in range(E):
    s, t = map(int, input().split())
    G[s].append(t)
component = scc_decomposition(G)
uf = UnionFind(2 * V)
for v in range(V):
    uf.unite(v, V + component[v])
Q = int(input())
for _ in range(Q):
    u, v = map(int, input().split())
    if uf.same(u, v):
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m = map(int, input().split())
    E = [[] for _ in range(n)]
    rev = [[] for _ in range(n)]
    outdeg = [0] * n
    for _ in range(m):
        u, v = map(int, input().split())
        E[u].append(v)
        rev[v].append(u)
        outdeg[u] += 1

    order = []
    used = [False] * n
    # for v in range(n):
    #     if used[v]:
    #         continue
    #     used[v] = True
    #     stack = [(~v, -1), (v, -1)]
    #     while stack:
    #         v, p = stack.pop()
    #         if v >= 0:
    #             for nv in E[v]:
    #                 if used[nv]:
    #                     outdeg[v] -= 1
    #                 else:
    #                     used[nv] = True
    #                     stack.append((~nv, v))
    #                     stack.append((nv, v))
    #         else:
    #             v = ~v
    #             if outdeg[v] == 0:
    #                 order.append(v)
    #             if p != -1:
    #                 outdeg[p] -= 1

    def dfs(v):
        if used[v]:
            return
        used[v] = True
        for nv in E[v]:
            dfs(nv)
        order.append(v)
    any(dfs(v) for v in range(n))
    order.reverse()
    color = [-1] * n
    ans = []
    cnt = -1
    for v in order:
        if color[v] != -1:
            continue
        cnt += 1
        color[v] = cnt
        stack = [v]
        while stack:
            v = stack.pop()
            for nv in rev[v]:
                if color[nv] != -1:
                    continue
                color[nv] = cnt
                stack.append(nv)

    for _ in range(int(input())):
        u, v = map(int, input().split())
        print(int(color[u] == color[v]))
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class StronglyConnectedComponents:
    def __init__(self,N):
        self.N = N
        self.G = [[] for _ in range(self.N)]
        self.rG = [[] for _ in range(self.N)]
        self.group = [1] * self.N
        self.order = []
    
    def add_edge(self,u,v): # u -> v
        self.G[u].append(v)
        self.rG[v].append(u)
    
    def build(self):
        stack = []
        for s in range(self.N):
            if self.group[s] > 0:
                stack.append(s + 1)
                while stack:
                    v = stack.pop()
                    if v < 0:
                        self.order.append(- v - 1)
                    else:
                        if self.group[v - 1] > 0:
                            stack.append(-v)
                            self.group[v - 1] = -1
                            for e in self.G[v - 1]:
                                stack.append(e + 1)
        
        cnt = 0
        for s in self.order[::-1]:
            if self.group[s] < 0:
                stack.append(s)
                self.group[s] = cnt
                while stack:
                    v = stack.pop()
                    for e in self.rG[v]:
                        if self.group[e] < 0:
                            self.group[e] = cnt
                            stack.append(e)
                cnt += 1
    
    def __getitem__(self,i):
        if 0 <= i < self.N:
            return self.group[i]
        else:
            raise ValueError("StrongglyConnectedComponents index out of range")

def main():
    V,E = map(int,input().split())
    scc = StronglyConnectedComponents(V)
    for _ in range(E):
        a,b = map(int,input().split())
        scc.add_edge(a,b)
    scc.build()

    Q = int(input())
    ans = []
    for _ in range(Q):
        u,v = map(int,input().split())
        if scc[u] == scc[v]:
            ans.append('1')
        else:
            ans.append('0')
    print('\n'.join(ans))
if __name__ == '__main__':
    main()