test/aoj/grl_4_a_2.test.cpp

View this file on GitHub
Last update: 2023-02-27 02:38:54+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_A

Depends on

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/search/bfs/has_directed_cycle.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 = has_directed_cycle(g);
  cout << (res ? 1 : 0) << endl;

  return 0;
}

#line 1 "test/aoj/grl_4_a_2.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/search/bfs/has_directed_cycle.hpp"

#line 4 "src/search/bfs/has_directed_cycle.hpp"
using namespace std;

#line 2 "src/search/bfs/topological_sort.hpp"

#line 4 "src/search/bfs/topological_sort.hpp"
using namespace std;

vector<int> topological_sort(const vector<vector<int>> &g) {
  int n = g.size();
  vector<int> deg(n);
  for (int i = 0; i < n; ++i) {
    for (int to : g[i]) {
      ++deg[to];
    }
  }
  queue<int> que;
  for (int i = 0; i < n; ++i) {
    if (deg[i] == 0) {
      que.push(i);
    }
  }
  vector<int> res;
  while (!que.empty()) {
    int v = que.front();
    que.pop();
    res.push_back(v);
    for (int to : g[v]) {
      --deg[to];
      if (deg[to] == 0) {
        que.push(to);
      }
    }
  }
  return res;
}
#line 7 "src/search/bfs/has_directed_cycle.hpp"

bool has_directed_cycle(const vector<vector<int>> &g) {
  vector<int> orders = topological_sort(g);
  int n = g.size();
  return (int)orders.size() != n;
}
#line 8 "test/aoj/grl_4_a_2.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 = has_directed_cycle(g);
  cout << (res ? 1 : 0) << endl;

  return 0;
}