test/aoj/scc.test.cpp

• View this file on GitHub
• Last update: 2024-07-11 22:21:57+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_C

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_C"
#include "include/mtl/scc.hpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
  int V,E; cin>>V>>E;
  SccGraph G(V);
  for (int i = 0; i < E; i++) {
    int s,t; cin>>s>>t;
    G.add_edge(s, t);
  }
  vector<int> id(V);
  auto scc = G.scc();
  for (int i = 0; i < (int) scc.size(); i++) {
    for (int u : scc[i])
      id[u] = i;
  }
  int Q; cin>>Q;
  for (int i = 0; i < Q; i++) {
    int u,v; cin>>u>>v;
    cout << (id[u] == id[v]) << endl;
  }
}

#line 1 "test/aoj/scc.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_C"
#line 2 "include/mtl/graph.hpp"
#include <queue>
#include <vector>

struct Graph {
  int n;
  std::vector<std::vector<int>> g;
  std::vector<int> in;
  std::vector<int> tour, L, R; // For Euler tour.

  Graph(int n) : n(n), g(n), in(n) {}

  void add_edge_dir(int a, int b) {
    g[a].push_back(b);
    in[b]++;
  }
  void add_edge(int a, int b) {
    add_edge_dir(a, b);
    add_edge_dir(b, a);
  }

  template <typename T> void bfs(int s, std::vector<T> &dist, T INF) const;
  template <typename T> bool topological_sort(std::vector<T> &order) const;
  void euler_tour(int root);
};

template <typename T>
void Graph::bfs(int s, std::vector<T> &dist, T INF) const {
  dist.assign(n, INF);
  std::queue<int> qs;
  dist[s] = 0;
  qs.push(s);
  while (!qs.empty()) {
    auto c = qs.front();
    qs.pop();
    auto d = dist[c];
    for (auto t : g[c]) {
      if (dist[t] <= d + 1)
        continue;
      dist[t] = d + 1;
      qs.push(t);
    }
  }
}

template <typename T>
bool Graph::topological_sort(std::vector<T> &order) const {
  order.resize(0);
  order.reserve(n);
  std::vector<int> incnt(n);
  auto dfs = [&](auto dfs, int s) -> void {
    order.push_back(s);
    for (auto t : g[s]) {
      if (++incnt[t] == in[t]) {
        dfs(dfs, t);
      }
    }
  };
  for (int i = 0; i < n; i++) {
    if (in[i] == 0)
      dfs(dfs, i);
  }
  return (int)order.size() == n;
}

void Graph::euler_tour(int root = 0) {
  tour.clear();
  L.resize(n);
  R.resize(n);
  auto dfs = [&](auto &f, int s, int p, int k) -> int {
    tour.push_back(s);
    L[s] = k;
    R[s] = k++;
    for (int t : g[s]) {
      if (t == p)
        continue;
      k = f(f, t, s, k);
      tour.push_back(s);
      R[s] = k++;
    }
    return k;
  };
  dfs(dfs, root, -1, 0);
}

template <typename W> struct Network {
  using weight_type = W;
  int n;
  struct Path {
    int t, w;
    Path(int t, W w) : t(t), w(w) {}
  };
  std::vector<std::vector<Path>> g;
  std::vector<int> in;

  Network(int n) : n(n), g(n), in(n) {}

  void add_edge_dir(int a, int b, W c) {
    g[a].emplace_back(b, c);
    in[b]++;
  }
  void add_edge(int a, int b, W c) {
    add_edge_dir(a, b, c);
    add_edge_dir(b, a, c);
  }

  template <typename T>
  void dijkstra_search(int s, std::vector<T> &dist, T INF) const;
};
#line 3 "include/mtl/scc.hpp"
#include <stack>

struct SccGraph {
  int n;
  Graph g,ig;
  explicit SccGraph(int n = 0) : n(n), g(n), ig(n) {}

  void add_edge(int a, int b) {
    g.add_edge_dir(a, b);
    ig.add_edge_dir(b, a);
  }

  std::vector<std::vector<int>> scc() const {
    std::vector<bool> vis(n);
    std::stack<int> st;

    auto dfs = [&](auto& f, int s) {
      if (vis[s]) return;
      vis[s] = true;
      for (int t:g.g[s])
        f(f, t);
      st.push(s);
    };
    for (int i = 0; i < n; i++)
      dfs(dfs, i);

    vis.assign(n, false);
    auto rdfs = [&](auto& f, int s, std::vector<int>& c) {
      if (vis[s]) return;
      vis[s] = true;
      for (int t:ig.g[s])
        f(f, t, c);
      c.push_back(s);
    };
    std::vector<std::vector<int>> ret;
    while (!st.empty()) {
      int u = st.top(); st.pop();
      if (vis[u]) continue;
      ret.emplace_back();
      rdfs(rdfs, u, ret.back());
    }
    return ret;
  }
};
#line 3 "test/aoj/scc.test.cpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
  int V,E; cin>>V>>E;
  SccGraph G(V);
  for (int i = 0; i < E; i++) {
    int s,t; cin>>s>>t;
    G.add_edge(s, t);
  }
  vector<int> id(V);
  auto scc = G.scc();
  for (int i = 0; i < (int) scc.size(); i++) {
    for (int u : scc[i])
      id[u] = i;
  }
  int Q; cin>>Q;
  for (int i = 0; i < Q; i++) {
    int u,v; cin>>u>>v;
    cout << (id[u] == id[v]) << endl;
  }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	5 ms	3 MB
g++	01_small_00.in	AC	5 ms	3 MB
g++	01_small_01.in	AC	5 ms	3 MB
g++	01_small_02.in	AC	5 ms	3 MB
g++	01_small_03.in	AC	5 ms	3 MB
g++	02_medium_00.in	AC	5 ms	3 MB
g++	02_medium_01.in	AC	5 ms	3 MB
g++	03_sparse_00.in	AC	5 ms	3 MB
g++	03_sparse_01.in	AC	5 ms	3 MB
g++	03_sparse_02.in	AC	6 ms	3 MB
g++	03_sparse_03.in	AC	6 ms	3 MB
g++	04_dense_00.in	AC	5 ms	3 MB
g++	04_dense_01.in	AC	6 ms	3 MB
g++	04_dense_02.in	AC	6 ms	3 MB
g++	04_dense_03.in	AC	12 ms	3 MB
g++	05_rand_00.in	AC	12 ms	4 MB
g++	05_rand_01.in	AC	12 ms	4 MB
g++	05_rand_02.in	AC	20 ms	4 MB
g++	06_linear_00.in	AC	85 ms	5 MB
g++	06_linear_01.in	AC	83 ms	5 MB
g++	07_linear_00.in	AC	83 ms	5 MB
g++	07_linear_01.in	AC	82 ms	5 MB
g++	08_grid_00.in	AC	103 ms	4 MB
g++	08_grid_01.in	AC	153 ms	5 MB
clang++	00_sample_00.in	AC	6 ms	3 MB
clang++	01_small_00.in	AC	5 ms	3 MB
clang++	01_small_01.in	AC	5 ms	3 MB
clang++	01_small_02.in	AC	5 ms	3 MB
clang++	01_small_03.in	AC	5 ms	3 MB
clang++	02_medium_00.in	AC	5 ms	3 MB
clang++	02_medium_01.in	AC	5 ms	3 MB
clang++	03_sparse_00.in	AC	5 ms	3 MB
clang++	03_sparse_01.in	AC	6 ms	3 MB
clang++	03_sparse_02.in	AC	6 ms	3 MB
clang++	03_sparse_03.in	AC	7 ms	3 MB
clang++	04_dense_00.in	AC	5 ms	3 MB
clang++	04_dense_01.in	AC	6 ms	3 MB
clang++	04_dense_02.in	AC	7 ms	3 MB
clang++	04_dense_03.in	AC	12 ms	3 MB
clang++	05_rand_00.in	AC	13 ms	4 MB
clang++	05_rand_01.in	AC	13 ms	4 MB
clang++	05_rand_02.in	AC	21 ms	4 MB
clang++	06_linear_00.in	AC	80 ms	5 MB
clang++	06_linear_01.in	AC	127 ms	5 MB
clang++	07_linear_00.in	AC	128 ms	5 MB
clang++	07_linear_01.in	AC	128 ms	5 MB
clang++	08_grid_00.in	AC	110 ms	4 MB
clang++	08_grid_01.in	AC	158 ms	5 MB

Back to top page