test/graph/scc.aoj_GRL_3_C.test.cpp

View this file on GitHub
Last update: 2022-07-07 14:50:02+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C

Depends on

Code

#define PROBLEM \
  "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C"

#include <iostream>
#include "graph/scc.hpp"
#include "graph/graphTemplate.hpp"
#include "macros.hpp"
using namespace std;

int main() {
  int V, E, Q;
  cin >> V >> E;
  Graph<int> G(V);
  G.read(E, 0, false, true);
  SCC<int> scc(G);
  cin >> Q;
  rep(i, Q) {
    int u, v;
    cin >> u >> v;
    cout << (scc.is_same(u, v) ? 1 : 0) << endl;
  }
}

#line 1 "test/graph/scc.aoj_GRL_3_C.test.cpp"
#define PROBLEM \
  "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C"

#include <iostream>
#line 2 "graph/scc.hpp"
#include <algorithm>
#include <unordered_map>
#include <vector>

#line 4 "graph/graphTemplate.hpp"
using namespace std;

template <typename T = int>
struct Edge {
  int from, to;
  T cost;
  int idx;
  Edge() = default;

  Edge(int from, int to, T cost = 1, int idx = -1)
      : from(from), to(to), cost(cost), idx(idx) {}
  operator int() const { return to; }
};

template <typename T = int>
struct Graph {
  vector<vector<Edge<T>>> g;
  int es;

  Graph() = default;
  explicit Graph(int n) : g(n), es(0) {}

  size_t size() const { return g.size(); }

  void add_directed_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es++);
  }

  void add_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es);
    g[to].emplace_back(to, from, cost, es++);
  }
  void read(int M, int padding = -1, bool weighted = false,
            bool directed = false) {
    for (int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      a += padding;
      b += padding;
      T c = T(1);
      if (weighted) {
        cin >> c;
      }
      if (directed) {
        add_directed_edge(a, b, c);
      } else {
        add_edge(a, b, c);
      }
    }
  }
  inline vector<Edge<T>> &operator[](const int &k) { return g[k]; }

  inline const vector<Edge<T>> &operator[](const int &k) const { return g[k]; }
};

template <typename T>
using Edges = vector<Edge<T>>;
#line 7 "graph/scc.hpp"
using namespace std;

template <typename T = int>
struct SCC {
public:
  int n;
  Graph<T> G;
  vector<int> component;
  SCC(Graph<T> &_G) {
    n = _G.size();
    G = _G;
    build();
  }

  void build() {
    rG = Graph(n);
    for(size_t i =0;i<n;i++){
      for(auto &e: G[i]) {
        rG.add_directed_edge(e.to, e.from, e.cost);
      }
    }
    component.assign(n, -1);
    used.assign(n, false);
    for (size_t v = 0; v < n; v++)
      if (!used[v]) dfs(v);
    reverse(order.begin(), order.end());
    int k = 0;
    for (auto v : order)
      if (component[v] == -1) rdfs(v, k), k++;
  }

  bool is_same(int u, int v) { return component[u] == component[v]; }

  long long count_pair() {
    unordered_map<int, long long> value_counts;
    for (int k : component) {
      value_counts[k]++;
    }
    long long ans = 0;
    for (auto x : value_counts) {
      ans += x.second * (x.second - 1) / 2;
    }
    return ans;
  }

private:
  Graph<T> rG;
  vector<int> order;
  vector<bool> used;

  void dfs(int v) {
    used[v] = 1;
    for (auto nv : G[v]) {
      if (!used[nv]) dfs(nv);
    }
    order.push_back(v);
  }

  void rdfs(int v, int k) {
    component[v] = k;
    for (auto nv : rG[v]) {
      if (component[nv] < 0) rdfs(nv, k);
    }
  }
};
#line 2 "macros.hpp"
#define rep(i, n) for (int i = 0; i < (n); i++)
#line 8 "test/graph/scc.aoj_GRL_3_C.test.cpp"
using namespace std;

int main() {
  int V, E, Q;
  cin >> V >> E;
  Graph<int> G(V);
  G.read(E, 0, false, true);
  SCC<int> scc(G);
  cin >> Q;
  rep(i, Q) {
    int u, v;
    cin >> u >> v;
    cout << (scc.is_same(u, v) ? 1 : 0) << endl;
  }
}