test/aoj/grl_3_c.test.cpp

View this file on GitHub
Last update: 2022-12-19 02:10:28+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_C

Depends on

Code

#define PROBLEM                                                                \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_C"

#include <bits/stdc++.h>
using namespace std;

#include "../../src/graph/strongly_connected_components.hpp"
#include "../../src/graph/template.hpp"

int main() {
  int V, E;
  cin >> V >> E;
  StronglyConnectedComponents scc(V);
  for (int i = 0; i < E; ++i) {
    int s, t;
    cin >> s >> t;
    scc.add_edge(s, t);
  }
  scc.build();
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; ++i) {
    int u, v;
    cin >> u >> v;
    cout << (scc[u] == scc[v] ? "1" : "0") << endl;
  }
  return 0;
}

#line 1 "test/aoj/grl_3_c.test.cpp"
#define PROBLEM                                                                \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_C"

#include <bits/stdc++.h>
using namespace std;

#line 2 "src/graph/strongly_connected_components.hpp"

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

#line 2 "src/graph/template.hpp"

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

template <typename T = long long> struct Edge {
  int from, to;
  T cost;
  Edge(int from, int to, T cost = 1) : from(from), to(to), cost(cost) {}
};

template <typename T = long long> using Edges = vector<Edge<T>>;
template <typename T = long long> using Graph = vector<Edges<T>>;

template <typename T = long long> using Matrix = vector<vector<T>>;
#line 7 "src/graph/strongly_connected_components.hpp"

struct StronglyConnectedComponents {
private:
  int n;
  Graph<> graph;
  Graph<> r_graph;
  vector<bool> used;
  vector<int> order, comp;

public:
  StronglyConnectedComponents(int n)
      : n(n), graph(n), r_graph(n), used(n, false), comp(n, -1) {}

  void add_edge(int u, int v) {
    graph[u].emplace_back(u, v);
    r_graph[v].emplace_back(v, u);
  }

  void build() {
    for (int i = 0; i < n; ++i) {
      if (!used[i]) {
        dfs(i);
      }
    }
    int cnt = 0;
    reverse(order.begin(), order.end());
    for (int i : order) {
      if (comp[i] == -1) {
        r_dfs(i, cnt++);
      }
    }
  }

  int operator[](int k) { return comp[k]; }

private:
  void dfs(int idx) {
    used[idx] = true;
    for (auto edge : graph[idx]) {
      if (!used[edge.to]) {
        dfs(edge.to);
      }
    }
    order.push_back(idx);
  }
  void r_dfs(int idx, int cnt) {
    comp[idx] = cnt;
    for (auto edge : r_graph[idx]) {
      if (comp[edge.to] == -1) {
        r_dfs(edge.to, cnt);
      }
    }
  }
};
#line 9 "test/aoj/grl_3_c.test.cpp"

int main() {
  int V, E;
  cin >> V >> E;
  StronglyConnectedComponents scc(V);
  for (int i = 0; i < E; ++i) {
    int s, t;
    cin >> s >> t;
    scc.add_edge(s, t);
  }
  scc.build();
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; ++i) {
    int u, v;
    cin >> u >> v;
    cout << (scc[u] == scc[v] ? "1" : "0") << endl;
  }
  return 0;
}