src/search/bfs/has_directed_cycle.hpp

View this file on GitHub
Last update: 2023-02-27 02:38:54+09:00
Include: #include "src/search/bfs/has_directed_cycle.hpp"

Depends on

src/search/bfs/topological_sort.hpp

Verified with

test/aoj/grl_4_a_2.test.cpp

Code

#pragma once

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

#include "./topological_sort.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 2 "src/search/bfs/has_directed_cycle.hpp"

#include <bits/stdc++.h>
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;
}