scc.cc

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits>
#include <functional>
#include <queue>
#include <stack>
#include <random>
#include <string>
#include <sstream>

#define rep(i, n) for (ll i=0; i < (n); ++i)
#define repr(i, n) for (ll i=(n)-1; i >= 0; --i)
#define ALL(c) (c).begin(), (c).end()

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

template<typename Vertex, typename Edges, typename Visited, typename Func1, typename Func2>
void dfs(
    const Vertex &v0,
    const Edges &edges,
    Visited &visited,
    const Func1 &process,
    const Func2 &postprocess) {

  if (visited[v0]) return;
  visited[v0] = true;
  process(v0);

  auto es = edges[v0];
  for (auto e = es.first; e != es.second; ++e) {
    if (!visited[e->second])
      dfs(e->second, edges, visited, process, postprocess);
  }

  postprocess(v0);
}

class Edges : private unordered_multimap<int, int> {
  public:
    void add(int from, int to) {
      insert(make_pair(from, to));
    }

    auto operator[](int from) const
      -> pair<unordered_multimap<int, int>::const_iterator, unordered_multimap<int, int>::const_iterator> {
      return equal_range(from);
    }
};

struct UnionFind {
  vector<int> v;

  UnionFind(int n) {
    v.resize(n);
    rep (i, n) {
      v[i] = i;
    }
  }

  bool unite(int i, int j) {
    int ir = find(i);
    int jr = find(j);
    v[i] = jr;
    return ir != jr;
  }

  int find(int i) {
    if (v[i] == i) {
      return i;
    } else {
      return v[i] = find(v[i]);
    }
  }

  bool same(int i, int j) {
    return find(i) == find(j);
  }
};

int main()
{
  int N, M;
  cin >> N >> M;
  Edges e;
  Edges t;
  while (M--) {
    int a, b;
    cin >> a >> b;
    e.add(a, b);
    t.add(b, a);
  }

  vector<int> visited(N);
  stack<int> stack;
  for (int i = 0; i <= N; i++){
    dfs(i, e, visited, [](int){}, [&stack](int v){ stack.push(v); });
  }

  UnionFind uf(N);
  fill(ALL(visited), 0);
  while (!stack.empty()) {
    int v = stack.top(); stack.pop();
    int prev = v;
    if (!visited[v]) {
      dfs(v, t, visited, [&uf, &prev](int v){ uf.unite(prev, v); prev = v; }, [](int){} );
    }
  }

  int Q;
  cin >> Q;
  while (Q--) {
    int i, j;
    cin >> i >> j;
    cout << uf.same(i, j) << endl;
  }
  return 0;
}