Cycle Detection
(graph/cycle-detection.hpp)

• View this file on GitHub
• Last update: 2026-09-05 04:46:11+09:00
• Include: #include "graph/cycle-detection.hpp"

有向グラフに含まれるサイクルを 1 つ求める．

各辺は行き先 to と辺番号 id を持つものとする．

• CycleDetection(g)：サイクルが存在すれば，通る順の辺番号列を返す．存在しなければ nullopt を返す．

反復 DFS により $O(N+M)$ 時間，$O(N)$ 空間．

Depends on

• Graph (graph/graph.hpp)

Verified with

• verify/graph/LC_cycle_detection.test.cpp

Code

#pragma once

#include "graph/graph.hpp"

template <class G>
optional<vector<int>> CycleDetection(const G& g) {
  int n = g.size();
  vector<unsigned char> state(n);
  vector<int> iter(n), path_pos(n), st, path;
  st.reserve(n);
  path.reserve(n);
  for (int root = 0; root < n; root++) {
    if (state[root] != 0) continue;
    state[root] = 1;
    path_pos[root] = 0;
    st.push_back(root);
    while (!st.empty()) {
      int x = st.back();
      if (iter[x] == static_cast<int>(g[x].size())) {
        state[x] = 2;
        st.pop_back();
        if (!st.empty()) path.pop_back();
        continue;
      }
      const auto& e = g[x][iter[x]++];
      int y = e.to;
      if (state[y] == 0) {
        state[y] = 1;
        path.push_back(e.id);
        path_pos[y] = path.size();
        st.push_back(y);
      } else if (state[y] == 1) {
        vector<int> cycle(path.begin() + path_pos[y], path.end());
        cycle.push_back(e.id);
        return cycle;
      }
    }
  }
  return nullopt;
}

/**
 * @brief Cycle Detection
 * @docs docs/graph/cycle-detection.md
 */

#line 2 "graph/cycle-detection.hpp"

#line 2 "graph/graph.hpp"

template <class E>
struct GraphBase {
 public:
  GraphBase() : GraphBase(0) {}
  GraphBase(int size) : n(size) {
    assert(size >= 0);
    g.resize(size);
  }
  size_t size() const { return n; }
  const vector<E>& operator[](int x) const {
    assert(0 <= x && x < n);
    return g[x];
  }
  vector<E>& operator[](int x) {
    assert(0 <= x && x < n);
    return g[x];
  }

 protected:
  int n;
  vector<vector<E>> g;
};

struct EdgeUnweighted {
  int to;
};
struct GraphUnweighted : GraphBase<EdgeUnweighted> {
  using base = GraphBase<EdgeUnweighted>;

 public:
  GraphUnweighted() : base(0) {}
  GraphUnweighted(int size) : base(size) {}
  GraphUnweighted(const vector<vector<int>>& graph) : base(graph.size()) {
    for (int x = 0; x < n; x++) {
      base::g[x].reserve(graph[x].size());
      for (int y : graph[x]) base::g[x].push_back({y});
    }
  }
  void add_edge(int x, int y) {
    (*this)[x].push_back({y});
    (*this)[y].push_back({x});
  }
  void add_edge_directed(int from, int to) { (*this)[from].push_back({to}); }
};

struct EdgeUnweightedIndexed {
  int to, id;
};
struct GraphUnweightedIndexed : GraphBase<EdgeUnweightedIndexed> {
  using base = GraphBase<EdgeUnweightedIndexed>;

 public:
  GraphUnweightedIndexed() : GraphUnweightedIndexed(0) {}
  GraphUnweightedIndexed(int size) : base(size), m(0) {}
  int edge_count() const { return m; }
  int add_edge(int x, int y) {
    int id = m++;
    (*this)[x].push_back({y, id});
    (*this)[y].push_back({x, id});
    return id;
  }
  int add_edge_directed(int from, int to) {
    int id = m++;
    (*this)[from].push_back({to, id});
    return id;
  }

 private:
  int m;
};

template <class T>
struct EdgeWeighted {
  int to;
  T weight;
};
template <class T>
struct GraphWeighted : GraphBase<EdgeWeighted<T>> {
  using base = GraphBase<EdgeWeighted<T>>;

 public:
  GraphWeighted() : base(0) {}
  GraphWeighted(int size) : base(size) {}
  GraphWeighted(const vector<vector<pair<int, T>>>& graph) : base(graph.size()) {
    for (int x = 0; x < base::n; x++) {
      base::g[x].reserve(graph[x].size());
      for (const auto& [y, w] : graph[x]) base::g[x].push_back({y, w});
    }
  }
  void add_edge(int x, int y, T w) {
    (*this)[x].push_back({y, w});
    (*this)[y].push_back({x, w});
  }
  void add_edge_directed(int from, int to, T w) { (*this)[from].push_back({to, w}); }
};

inline GraphWeighted<int> GraphUnweightedToWeighted(const GraphUnweighted& g) {
  GraphWeighted<int> h(g.size());
  for (int x = 0; x < static_cast<int>(g.size()); x++) {
    h[x].reserve(g[x].size());
    for (const auto& e : g[x]) h[x].push_back({e.to, 1});
  }
  return h;
}

/**
 * @brief Graph
 * @docs docs/graph/graph.md
 */
#line 4 "graph/cycle-detection.hpp"

template <class G>
optional<vector<int>> CycleDetection(const G& g) {
  int n = g.size();
  vector<unsigned char> state(n);
  vector<int> iter(n), path_pos(n), st, path;
  st.reserve(n);
  path.reserve(n);
  for (int root = 0; root < n; root++) {
    if (state[root] != 0) continue;
    state[root] = 1;
    path_pos[root] = 0;
    st.push_back(root);
    while (!st.empty()) {
      int x = st.back();
      if (iter[x] == static_cast<int>(g[x].size())) {
        state[x] = 2;
        st.pop_back();
        if (!st.empty()) path.pop_back();
        continue;
      }
      const auto& e = g[x][iter[x]++];
      int y = e.to;
      if (state[y] == 0) {
        state[y] = 1;
        path.push_back(e.id);
        path_pos[y] = path.size();
        st.push_back(y);
      } else if (state[y] == 1) {
        vector<int> cycle(path.begin() + path_pos[y], path.end());
        cycle.push_back(e.id);
        return cycle;
      }
    }
  }
  return nullopt;
}

/**
 * @brief Cycle Detection
 * @docs docs/graph/cycle-detection.md
 */

Back to top page