Cycle Detection
(graph/cycle_detection.hpp)

View this file on GitHub
Last update: 2026-08-13 01:41:40+09:00
Include: #include "graph/cycle_detection.hpp"

Overview

Cycle detection finds one cycle, if the graph contains any. A cycle is returned as both vertices and edge ids, which is convenient for problems that ask you to output the actual cycle.

There are separate functions for directed and undirected graphs because the DFS rules are different:

in a directed graph, an edge to a currently active DFS vertex forms a cycle;
in an undirected graph, the DFS must ignore only the exact edge used to enter the current vertex.

Graph Orientation

This header has both variants:

find_directed_cycle(g) respects edge direction;
find_undirected_cycle(g) treats edges as undirected and should be used with graphs built by add_edge.

How to Use It

Use find_directed_cycle(g) for graphs built with add_directed_edge. Use find_undirected_cycle(g) for graphs built with add_edge.

The result type is Cycle.

Member	Type / Signature	Meaning
`vertices`	`std::vector<int>`	Cycle vertices, with the first vertex repeated at the end. Empty if no cycle exists.
`edge_ids`	`std::vector<int>`	Edge ids used along the cycle. Its size is `vertices.size() - 1` when non-empty.
`empty`	`bool empty() const`	Returns whether no cycle was found.

The returned cycle is not guaranteed to be the shortest one; it is simply the first cycle found by the DFS.

Functions

Function	Signature	Description	Complexity
`find_directed_cycle`	`template <class T> Cycle find_directed_cycle(const Graph<T>& g)`	Finds a directed cycle.	$O(N + M)$
`find_undirected_cycle`	`template <class T> Cycle find_undirected_cycle(const Graph<T>& g)`	Finds an undirected cycle.	$O(N + M)$

Example

#include "graph/cycle_detection.hpp"
#include "graph/graph.hpp"
#include <iostream>

int main() {
    m1une::graph::Graph<> g(3);
    g.add_directed_edge(0, 1);
    g.add_directed_edge(1, 2);
    g.add_directed_edge(2, 0);

    auto cycle = m1une::graph::find_directed_cycle(g);
    if (!cycle.empty()) {
        for (int v : cycle.vertices) std::cout << v << " ";
        std::cout << "\n";
    }
}

Depends on

Graph (graph/graph.hpp)

Required by

Verified with

Code

#ifndef M1UNE_GRAPH_CYCLE_DETECTION_HPP
#define M1UNE_GRAPH_CYCLE_DETECTION_HPP 1

#include <algorithm>
#include <cstddef>
#include <vector>

#include "graph.hpp"

namespace m1une {
namespace graph {

struct Cycle {
    std::vector<int> vertices;
    std::vector<int> edge_ids;

    bool empty() const {
        return vertices.empty();
    }
};

inline Cycle restore_cycle(int from, int to, int closing_edge, const std::vector<int>& parent,
                           const std::vector<int>& parent_edge) {
    Cycle result;
    result.vertices.push_back(to);

    std::vector<int> middle_vertices;
    std::vector<int> middle_edges;
    for (int v = from; v != to; v = parent[v]) {
        middle_vertices.push_back(v);
        middle_edges.push_back(parent_edge[v]);
    }
    std::reverse(middle_vertices.begin(), middle_vertices.end());
    std::reverse(middle_edges.begin(), middle_edges.end());

    result.vertices.insert(result.vertices.end(), middle_vertices.begin(), middle_vertices.end());
    result.vertices.push_back(to);
    result.edge_ids.insert(result.edge_ids.end(), middle_edges.begin(), middle_edges.end());
    result.edge_ids.push_back(closing_edge);
    return result;
}

template <class T>
Cycle find_directed_cycle(const Graph<T>& g) {
    int n = g.size();
    std::vector<int> color(n, 0), parent(n, -1), parent_edge(n, -1);
    struct Frame {
        int vertex;
        std::size_t next_edge;
    };

    std::vector<Frame> stack;
    stack.reserve(n);
    for (int start = 0; start < n; start++) {
        if (color[start] != 0) continue;
        color[start] = 1;
        stack.push_back(Frame{start, 0});
        while (!stack.empty()) {
            Frame& frame = stack.back();
            const int vertex = frame.vertex;
            const auto& adjacency = g[vertex];
            while (
                frame.next_edge < adjacency.size() &&
                !adjacency[frame.next_edge].alive
            ) {
                frame.next_edge++;
            }
            if (frame.next_edge == adjacency.size()) {
                color[vertex] = 2;
                stack.pop_back();
                continue;
            }

            const auto& edge = adjacency[frame.next_edge++];
            const int to = edge.to;
            const int edge_id = edge.id;
            if (color[to] == 0) {
                parent[to] = vertex;
                parent_edge[to] = edge_id;
                color[to] = 1;
                stack.push_back(Frame{to, 0});
            } else if (color[to] == 1) {
                return restore_cycle(vertex, to, edge_id, parent, parent_edge);
            }
        }
    }
    return Cycle();
}

template <class T>
Cycle find_undirected_cycle(const Graph<T>& g) {
    int n = g.size();
    std::vector<int> color(n, 0), parent(n, -1), parent_edge(n, -1);
    struct Frame {
        int vertex;
        std::size_t next_edge;
    };

    std::vector<Frame> stack;
    stack.reserve(n);
    for (int start = 0; start < n; start++) {
        if (color[start] != 0) continue;
        color[start] = 1;
        stack.push_back(Frame{start, 0});
        while (!stack.empty()) {
            Frame& frame = stack.back();
            const int vertex = frame.vertex;
            const auto& adjacency = g[vertex];
            while (
                frame.next_edge < adjacency.size() &&
                (
                    !adjacency[frame.next_edge].alive ||
                    adjacency[frame.next_edge].id == parent_edge[vertex]
                )
            ) {
                frame.next_edge++;
            }
            if (frame.next_edge == adjacency.size()) {
                color[vertex] = 2;
                stack.pop_back();
                continue;
            }

            const auto& edge = adjacency[frame.next_edge++];
            const int to = edge.to;
            const int edge_id = edge.id;
            if (color[to] == 0) {
                parent[to] = vertex;
                parent_edge[to] = edge_id;
                color[to] = 1;
                stack.push_back(Frame{to, 0});
            } else if (color[to] == 1) {
                return restore_cycle(vertex, to, edge_id, parent, parent_edge);
            }
        }
    }
    return Cycle();
}

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_CYCLE_DETECTION_HPP

#line 1 "graph/cycle_detection.hpp"



#include <algorithm>
#include <cstddef>
#include <vector>

#line 1 "graph/graph.hpp"



#include <array>
#include <cassert>
#include <utility>
#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


#line 9 "graph/cycle_detection.hpp"

namespace m1une {
namespace graph {

struct Cycle {
    std::vector<int> vertices;
    std::vector<int> edge_ids;

    bool empty() const {
        return vertices.empty();
    }
};

inline Cycle restore_cycle(int from, int to, int closing_edge, const std::vector<int>& parent,
                           const std::vector<int>& parent_edge) {
    Cycle result;
    result.vertices.push_back(to);

    std::vector<int> middle_vertices;
    std::vector<int> middle_edges;
    for (int v = from; v != to; v = parent[v]) {
        middle_vertices.push_back(v);
        middle_edges.push_back(parent_edge[v]);
    }
    std::reverse(middle_vertices.begin(), middle_vertices.end());
    std::reverse(middle_edges.begin(), middle_edges.end());

    result.vertices.insert(result.vertices.end(), middle_vertices.begin(), middle_vertices.end());
    result.vertices.push_back(to);
    result.edge_ids.insert(result.edge_ids.end(), middle_edges.begin(), middle_edges.end());
    result.edge_ids.push_back(closing_edge);
    return result;
}

template <class T>
Cycle find_directed_cycle(const Graph<T>& g) {
    int n = g.size();
    std::vector<int> color(n, 0), parent(n, -1), parent_edge(n, -1);
    struct Frame {
        int vertex;
        std::size_t next_edge;
    };

    std::vector<Frame> stack;
    stack.reserve(n);
    for (int start = 0; start < n; start++) {
        if (color[start] != 0) continue;
        color[start] = 1;
        stack.push_back(Frame{start, 0});
        while (!stack.empty()) {
            Frame& frame = stack.back();
            const int vertex = frame.vertex;
            const auto& adjacency = g[vertex];
            while (
                frame.next_edge < adjacency.size() &&
                !adjacency[frame.next_edge].alive
            ) {
                frame.next_edge++;
            }
            if (frame.next_edge == adjacency.size()) {
                color[vertex] = 2;
                stack.pop_back();
                continue;
            }

            const auto& edge = adjacency[frame.next_edge++];
            const int to = edge.to;
            const int edge_id = edge.id;
            if (color[to] == 0) {
                parent[to] = vertex;
                parent_edge[to] = edge_id;
                color[to] = 1;
                stack.push_back(Frame{to, 0});
            } else if (color[to] == 1) {
                return restore_cycle(vertex, to, edge_id, parent, parent_edge);
            }
        }
    }
    return Cycle();
}

template <class T>
Cycle find_undirected_cycle(const Graph<T>& g) {
    int n = g.size();
    std::vector<int> color(n, 0), parent(n, -1), parent_edge(n, -1);
    struct Frame {
        int vertex;
        std::size_t next_edge;
    };

    std::vector<Frame> stack;
    stack.reserve(n);
    for (int start = 0; start < n; start++) {
        if (color[start] != 0) continue;
        color[start] = 1;
        stack.push_back(Frame{start, 0});
        while (!stack.empty()) {
            Frame& frame = stack.back();
            const int vertex = frame.vertex;
            const auto& adjacency = g[vertex];
            while (
                frame.next_edge < adjacency.size() &&
                (
                    !adjacency[frame.next_edge].alive ||
                    adjacency[frame.next_edge].id == parent_edge[vertex]
                )
            ) {
                frame.next_edge++;
            }
            if (frame.next_edge == adjacency.size()) {
                color[vertex] = 2;
                stack.pop_back();
                continue;
            }

            const auto& edge = adjacency[frame.next_edge++];
            const int to = edge.to;
            const int edge_id = edge.id;
            if (color[to] == 0) {
                parent[to] = vertex;
                parent_edge[to] = edge_id;
                color[to] = 1;
                stack.push_back(Frame{to, 0});
            } else if (color[to] == 1) {
                return restore_cycle(vertex, to, edge_id, parent, parent_edge);
            }
        }
    }
    return Cycle();
}

}  // namespace graph
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Cycle Detection
(graph/cycle_detection.hpp)

Overview

Graph Orientation

How to Use It

Functions

Example

Depends on

Required by

Verified with

Code

Cycle Detection (graph/cycle_detection.hpp)

Overview

Graph Orientation

How to Use It

Functions

Example

Depends on

Required by

Verified with

Code

Cycle Detection
(graph/cycle_detection.hpp)