サイクル検出
(library/graph/cycle.hpp)

• View this file on GitHub
• Last update: 2025-08-17 00:21:01+09:00
• Include: #include "library/graph/cycle.hpp"

サイクル検出

辺素なサイクルを 1 つ検出する。

見つかった場合、 (頂点 index リスト, 辺 index リスト) を返す。 なければ nullopt を返す。

リストの長さを $L$ とすると、 $v_0 \to v_1 \to \cdots \to v_{L-1} \to v_0$ がサイクルになる。 $e_i$ は $v_{i} \to v_{i+1}$ を表す。 頂点 index リストと辺 index リストの長さは等しい。

$O(n + m)$

• cycle(size_t n, T edge_list, bool is_directed = false) -> optional<pair<vector<size_t>, vector<size_t>>>

頂点数と辺 (pair or tuple で get<0>, get<1> が頂点となる) リストを与える。

Depends on

• library/_internal/graph-base.hpp

Verified with

• tests/graph/cycle/libchecker-directed.test.cpp
• tests/graph/cycle/libchecker-undirected.test.cpp

Code

#pragma once

#include <algorithm>
#include <cassert>
#include <functional>
#include <optional>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

#include "../_internal/graph-base.hpp"

namespace asalib::graph {
  template<_internal::edge_list T>
  optional<pair<vector<size_t>, vector<size_t>>> cycle(const size_t n_vertex, const T& edgelist, const bool is_directed = false) {
    vector adj_list(n_vertex, vector<pair<size_t, size_t>>());
    rep(i, edgelist.size()) {
      size_t u = get<0>(edgelist[i]), v = get<1>(edgelist[i]);
      assert(u < n_vertex);
      assert(v < n_vertex);
      adj_list[u].emplace_back(v, i);
      if (!is_directed) adj_list[v].emplace_back(u, i);
    }

    vector visited(n_vertex, false);
    vector finished(n_vertex, false);
    vector<bool> used(edgelist.size(), false);
    stack<size_t> st;
    size_t base_point = -1;

    function<bool(size_t)> dfs = [&](const size_t v) -> bool {
      visited[v] = true;
      for (auto [to, edge_id] : adj_list[v]) {
        if (used[edge_id]) continue;
        used[edge_id] = true;
        st.emplace(edge_id);
        if (!finished[to] && visited[to]) {
          base_point = to;
          return true;
        }
        if (!visited[to] && dfs(to)) return true;
        st.pop();
        used[edge_id] = false;
      }
      finished[v] = true;
      return false;
    };

    for (size_t i = 0; i < n_vertex; ++i) {
      if (!visited[i]) {
        if (dfs(i)) {
          size_t v = base_point;
          vector<size_t> edges, verts;
          while (!st.empty()) {
            size_t edge_id = st.top();
            st.pop();
            edges.emplace_back(edge_id);
            if (is_directed) {
              assert(edgelist[edge_id].second == v);
              v = edgelist[edge_id].first;
            }
            else {
              assert(edgelist[edge_id].first == v || edgelist[edge_id].second == v);
              v = (edgelist[edge_id].first == v ? edgelist[edge_id].second : edgelist[edge_id].first);
            }
            verts.emplace_back(v);
            if (v == base_point) break;
          }
          ranges::reverse(verts);
          ranges::reverse(edges);
          assert(verts.size() == edges.size());
          assert(verts[0] == base_point);
          return make_pair(verts, edges);
        }
      }
    }
    return nullopt;
  }
}  // namespace asalib::graph

#line 2 "library/graph/cycle.hpp"

#include <algorithm>
#include <cassert>
#include <functional>
#include <optional>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

#line 2 "library/_internal/graph-base.hpp"

#include <concepts>
#include <cstddef>
#include <ranges>
#line 7 "library/_internal/graph-base.hpp"
using namespace std;

namespace asalib::_internal {
  // vector<vector<int>> とかの隣接リストを表す型
  template<class T>
  concept adjacency_list = requires(T t) {
    { t.size() } -> convertible_to<size_t>;
    { t[0] } -> ranges::range;
    { *ranges::begin(t[0]) } -> convertible_to<size_t>;
  };

  // 辺のリストを表す型
  // 重み付きも考慮し pair<int, int> と tuple<int, int, int> の両方を許容
  template<class T>
  concept edge_list = requires(T t) {
    { t.size() } -> convertible_to<size_t>;
    { get<0>(t[0]) } -> convertible_to<size_t>;
    { get<1>(t[0]) } -> convertible_to<size_t>;
  };
}  // namespace asalib::_internal
#line 13 "library/graph/cycle.hpp"

namespace asalib::graph {
  template<_internal::edge_list T>
  optional<pair<vector<size_t>, vector<size_t>>> cycle(const size_t n_vertex, const T& edgelist, const bool is_directed = false) {
    vector adj_list(n_vertex, vector<pair<size_t, size_t>>());
    rep(i, edgelist.size()) {
      size_t u = get<0>(edgelist[i]), v = get<1>(edgelist[i]);
      assert(u < n_vertex);
      assert(v < n_vertex);
      adj_list[u].emplace_back(v, i);
      if (!is_directed) adj_list[v].emplace_back(u, i);
    }

    vector visited(n_vertex, false);
    vector finished(n_vertex, false);
    vector<bool> used(edgelist.size(), false);
    stack<size_t> st;
    size_t base_point = -1;

    function<bool(size_t)> dfs = [&](const size_t v) -> bool {
      visited[v] = true;
      for (auto [to, edge_id] : adj_list[v]) {
        if (used[edge_id]) continue;
        used[edge_id] = true;
        st.emplace(edge_id);
        if (!finished[to] && visited[to]) {
          base_point = to;
          return true;
        }
        if (!visited[to] && dfs(to)) return true;
        st.pop();
        used[edge_id] = false;
      }
      finished[v] = true;
      return false;
    };

    for (size_t i = 0; i < n_vertex; ++i) {
      if (!visited[i]) {
        if (dfs(i)) {
          size_t v = base_point;
          vector<size_t> edges, verts;
          while (!st.empty()) {
            size_t edge_id = st.top();
            st.pop();
            edges.emplace_back(edge_id);
            if (is_directed) {
              assert(edgelist[edge_id].second == v);
              v = edgelist[edge_id].first;
            }
            else {
              assert(edgelist[edge_id].first == v || edgelist[edge_id].second == v);
              v = (edgelist[edge_id].first == v ? edgelist[edge_id].second : edgelist[edge_id].first);
            }
            verts.emplace_back(v);
            if (v == base_point) break;
          }
          ranges::reverse(verts);
          ranges::reverse(edges);
          assert(verts.size() == edges.size());
          assert(verts[0] == base_point);
          return make_pair(verts, edges);
        }
      }
    }
    return nullopt;
  }
}  // namespace asalib::graph

Back to top page