test/aoj/grl/grl_3_c.test.cpp

• View this file on GitHub
• Last update: 2022-07-20 01:33:22+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C

Depends on

• 強連結成分分解 (graph/strongly_connected_components.hpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C"
#include <bits/stdc++.h>
using namespace std;
#include "../../../graph/strongly_connected_components.hpp"
int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> E(N);
  for (int i = 0; i < M; i++){
    int s, t;
    cin >> s >> t;
    E[s].push_back(t);
  }
  strongly_connected_components G(E);
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++){
    int u, v;
    cin >> u >> v;
    if (G[u] == G[v]){
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
  }
}

#line 1 "test/aoj/grl/grl_3_c.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C"
#include <bits/stdc++.h>
using namespace std;
#line 2 "graph/strongly_connected_components.hpp"
/**
 * @brief 強連結成分分解
*/
struct strongly_connected_components{
  vector<int> scc;
  int cnt = 0;
  void dfs1(vector<vector<int>> &E, vector<int> &t, vector<bool> &used, int v){
    for (int w : E[v]){
      if (!used[w]){
        used[w] = true;
        dfs1(E, t, used, w);
      }
    }
    t.push_back(v);
  }
  void dfs2(vector<vector<int>> &E2, vector<bool> &used2, int v){
    scc[v] = cnt;
    for (int w : E2[v]){
      if (!used2[w]){
        used2[w] = true;
        dfs2(E2, used2, w);
      }
    }
  }
  strongly_connected_components(vector<vector<int>> &E){
    int N = E.size();
    vector<vector<int>> E2(N);
    for (int i = 0; i < N; i++){
      for (int j : E[i]){
        E2[j].push_back(i);
      }
    }
    vector<int> t;
    vector<bool> used(N, false);
    for (int i = 0; i < N; i++){
      if (!used[i]){
        used[i] = true;
        dfs1(E, t, used, i);
      }
    }
    reverse(t.begin(), t.end());
    vector<bool> used2(N, false);
    scc = vector<int>(N);
    for (int i = 0; i < N; i++){
      if (!used2[t[i]]){
        used2[t[i]] = true;
        dfs2(E2, used2, t[i]);
        cnt++;
      }
    }
  }
  int operator [](int k){
    return scc[k];
  }
};
#line 5 "test/aoj/grl/grl_3_c.test.cpp"
int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> E(N);
  for (int i = 0; i < M; i++){
    int s, t;
    cin >> s >> t;
    E[s].push_back(t);
  }
  strongly_connected_components G(E);
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++){
    int u, v;
    cin >> u >> v;
    if (G[u] == G[v]){
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
  }
}

Back to top page