test/aoj/grl_4_a.test.cpp

View this file on GitHub
Last update: 2023-01-28 17:23:21+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_A

Depends on

src/graph/cycle_detection.hpp

Code

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

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

#include "../../src/graph/cycle_detection.hpp"

int main() {
  int V, E;
  cin >> V >> E;
  vector<vector<int>> g(V);
  for (int i = 0; i < E; ++i) {
    int s, t;
    cin >> s >> t;
    g[s].push_back(t);
  }
  auto res = cycle_detection(g);
  cout << (res ? 1 : 0) << endl;

  return 0;
}

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

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

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

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

template <typename T = int> bool cycle_detection(vector<vector<int>> g) {
  bool has_cycle = false;
  vector<bool> seen(g.size());
  vector<bool> finished(g.size());
  auto dfs = [&](auto dfs, int v, int parent) -> void {
    seen[v] = true;
    for (int to : g[v]) {
      if (to == parent) {
        continue;
      }
      if (finished[to]) {
        continue;
      }
      if (seen[to] && !finished[to]) {
        has_cycle = true;
        return;
      }
      dfs(dfs, to, v);
      if (has_cycle) {
        return;
      }
    }
    finished[v] = true;
  };
  for (int v = 0; v < (int)g.size(); ++v) {
    if (seen[v]) {
      continue;
    }
    dfs(dfs, v, -1);
  }
  return has_cycle;
}
#line 8 "test/aoj/grl_4_a.test.cpp"

int main() {
  int V, E;
  cin >> V >> E;
  vector<vector<int>> g(V);
  for (int i = 0; i < E; ++i) {
    int s, t;
    cin >> s >> t;
    g[s].push_back(t);
  }
  auto res = cycle_detection(g);
  cout << (res ? 1 : 0) << endl;

  return 0;
}