Cycle Detect(サイクル検出)
(graph/cycle-detect.hpp)

• View this file on GitHub
• Last update: 2023-03-13 02:01:43+09:00
• Include: #include "graph/cycle-detect.hpp"

説明

• 閉路を検出し、そのうち１つの閉路の頂点集合を返す

• 閉路が存在しなければ、空の配列を返す

• Constructor

  Cycle (const graph &_g)
  

• 閉路検出

  vector<Edge<int>> Cycle::detect()
  

Depends on

• Graph Template (graph/template.hpp)

Verified with

• test/yosupo/Graph/Cycle-Detection(Directed).test.cpp

Code

#include "template.hpp"

struct Cycle {
  Cycle(const graph &_g) : g(_g){}
  vector<Edge<int>> detect(){
    const int n = g.size();
    used.assign(n, 0);
    prev.assign(n, -1);
    for(int i = 0; i < n; i++){
      if(!used[i] && dfs(i)){
        reverse(cyc.begin(), cyc.end());
        return cyc;
      }
    }
    return {};
  }
  private:
  const graph &g;
  vector<int> used;
  vector<Edge<int>> prev, cyc;
  bool dfs(int pos){
    used[pos] = 1;
    for(const auto &x : g[pos]){
      if(!used[x]){
        prev[x] = x;
        if(dfs(x)) return true;
      }else if(used[x] == 1){
        int cur = pos;
        cyc.push_back(x);
        while(cur != x){
          cyc.push_back(prev[cur]);
          cur = prev[cur].from;
        }
        return true;
      }
    }
    used[pos] = 2;
    return false;
  }
};

#line 2 "graph/template.hpp"

/**
 * @brief Graph Template
*/
template <class T>
struct Edge {
  int from,to;
  T cost;
  int idx;
  Edge(){};
  Edge(int f, int t, T c=1, int i=-1) : from(f), to(t), cost(c), idx(i){}
  Edge(int t) : to(t), from(-1), cost(1), idx(-1){}
  operator int() const{ return to; }
  bool operator<(const Edge &e){ return cost < e.cost; }
};
template <class T>
struct Graph : vector<vector<Edge<T>>> {
  Graph(){}
  Graph(const int &n) : vector<vector<Edge<T>>>(n){}
  void add_edge(int a, int b, T c=1, int i=-1){
    (*this)[a].push_back({ a, b, c, i });
  }
};
using graph = Graph<int>;
#line 2 "graph/cycle-detect.hpp"

struct Cycle {
  Cycle(const graph &_g) : g(_g){}
  vector<Edge<int>> detect(){
    const int n = g.size();
    used.assign(n, 0);
    prev.assign(n, -1);
    for(int i = 0; i < n; i++){
      if(!used[i] && dfs(i)){
        reverse(cyc.begin(), cyc.end());
        return cyc;
      }
    }
    return {};
  }
  private:
  const graph &g;
  vector<int> used;
  vector<Edge<int>> prev, cyc;
  bool dfs(int pos){
    used[pos] = 1;
    for(const auto &x : g[pos]){
      if(!used[x]){
        prev[x] = x;
        if(dfs(x)) return true;
      }else if(used[x] == 1){
        int cur = pos;
        cyc.push_back(x);
        while(cur != x){
          cyc.push_back(prev[cur]);
          cur = prev[cur].from;
        }
        return true;
      }
    }
    used[pos] = 2;
    return false;
  }
};

Back to top page