Two-Edge-Connected Components
(graph/two_edge_connected_components.hpp)

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

Overview

Two connected vertices are in the same two-edge-connected component when deleting any single edge cannot separate them. Equivalently, remove every bridge and take the connected components that remain.

This header returns that decomposition, all bridge IDs, and the forest obtained by contracting every component. Each contracted edge remembers the ID of its original bridge.

Graph Requirements

Build the undirected graph with Graph<T>::add_edge. Directed edges are not supported. Parallel edges and self-loops are supported: parallel edges prevent each other from being bridges, and a self-loop is never a bridge.

Inactive edges are ignored. They are not reported as bridges and do not connect components.

Both traversals are iterative, so deep paths do not consume the call stack.

API

struct TwoEdgeConnectedBridge {
    int from;
    int to;
    int edge_id;
};

struct TwoEdgeConnectedComponentsResult {
    std::vector<std::vector<int>> components;
    std::vector<int> component_of_vertex;
    std::vector<int> bridge_ids;
    std::vector<char> bridge;
    std::vector<TwoEdgeConnectedBridge> bridge_forest_edges;
    std::vector<int> ord;
    std::vector<int> low;

    int component_count() const;
    bool same(int first, int second) const;
    bool is_bridge(int edge_id) const;
};

template <class T>
TwoEdgeConnectedComponentsResult two_edge_connected_components(
    const Graph<T>& graph
);

Member or function	Description	Complexity
`components[c]`	Vertices in component `c`; their order is unspecified.	–
`component_of_vertex[v]`	Component containing vertex `v`.	$O(1)$
`bridge_ids`	Active bridge IDs in increasing edge-ID order.	–
`bridge[e]`	Nonzero exactly when active edge `e` is a bridge.	$O(1)$
`bridge_forest_edges`	Component-to-component edges after contraction, with original bridge IDs.	–
`ord[v]`, `low[v]`	DFS order and lowlink value of vertex `v`.	$O(1)$
`component_count()`	Number of two-edge-connected components.	$O(1)$
`same(u, v)`	Whether `u` and `v` belong to the same component.	$O(1)$
`is_bridge(edge_id)`	Whether the active edge is a bridge; inactive edges return false.	$O(1)$
`two_edge_connected_components(graph)`	Computes the decomposition and bridge forest.	$O(N + M)$

The function does not mutate the graph and uses $O(N + M)$ memory.

Example

#include "graph/graph.hpp"
#include "graph/two_edge_connected_components.hpp"

#include <iostream>

int main() {
    m1une::graph::Graph<> graph(4);
    graph.add_edge(0, 1);
    graph.add_edge(1, 2);
    graph.add_edge(2, 0);
    int bridge = graph.add_edge(2, 3);

    auto result = m1une::graph::two_edge_connected_components(graph);
    std::cout << result.component_count() << "\n";  // 2
    std::cout << result.same(0, 2) << "\n";          // 1
    std::cout << result.is_bridge(bridge) << "\n";   // 1
}

Depends on

Graph (graph/graph.hpp)

Required by

Verified with

Code

#ifndef M1UNE_GRAPH_TWO_EDGE_CONNECTED_COMPONENTS_HPP
#define M1UNE_GRAPH_TWO_EDGE_CONNECTED_COMPONENTS_HPP 1

#include <cassert>
#include <vector>

#include "graph.hpp"

namespace m1une {
namespace graph {

struct TwoEdgeConnectedBridge {
    int from;
    int to;
    int edge_id;
};

struct TwoEdgeConnectedComponentsResult {
    std::vector<std::vector<int>> components;
    std::vector<int> component_of_vertex;
    std::vector<int> bridge_ids;
    std::vector<char> bridge;
    std::vector<TwoEdgeConnectedBridge> bridge_forest_edges;
    std::vector<int> ord;
    std::vector<int> low;

    int component_count() const {
        return int(components.size());
    }

    bool same(int first, int second) const {
        assert(0 <= first && first < int(component_of_vertex.size()));
        assert(0 <= second && second < int(component_of_vertex.size()));
        return component_of_vertex[first] == component_of_vertex[second];
    }

    bool is_bridge(int edge_id) const {
        assert(0 <= edge_id && edge_id < int(bridge.size()));
        return bridge[edge_id];
    }
};

// Removes every active bridge and returns the remaining connected components.
// The first lowlink traversal and the component traversal are both iterative.
template <class T>
TwoEdgeConnectedComponentsResult two_edge_connected_components(
    const Graph<T>& graph
) {
    const int n = graph.size();
    const int edge_count = graph.edge_count();

    TwoEdgeConnectedComponentsResult result;
    result.component_of_vertex.assign(n, -1);
    result.bridge.assign(edge_count, false);
    result.ord.assign(n, -1);
    result.low.assign(n, -1);

    std::vector<int> edge_from(edge_count, -1);
    std::vector<int> edge_to(edge_count, -1);
    std::vector<int> incidence_count(edge_count, 0);
    for (int vertex = 0; vertex < n; vertex++) {
        for (const Edge<T>& edge : graph[vertex]) {
            if (!edge.alive) continue;
            assert(0 <= edge.id && edge.id < edge_count);
            if (incidence_count[edge.id] == 0) {
                edge_from[edge.id] = edge.from;
                edge_to[edge.id] = edge.to;
            }
            incidence_count[edge.id]++;
        }
    }
#ifndef NDEBUG
    for (int edge_id = 0; edge_id < edge_count; edge_id++) {
        if (incidence_count[edge_id] != 0) assert(incidence_count[edge_id] == 2);
    }
#endif

    std::vector<int> parent(n, -1);
    std::vector<int> parent_edge(n, -1);
    std::vector<int> next_edge(n, 0);
    std::vector<int> stack;
    int timer = 0;

    for (int root = 0; root < n; root++) {
        if (result.ord[root] != -1) continue;
        result.ord[root] = result.low[root] = timer++;
        stack.push_back(root);
        while (!stack.empty()) {
            const int vertex = stack.back();
            if (next_edge[vertex] < int(graph[vertex].size())) {
                const Edge<T>& edge = graph[vertex][next_edge[vertex]++];
                if (!edge.alive || edge.id == parent_edge[vertex]) continue;
                const int to = edge.to;
                if (result.ord[to] == -1) {
                    parent[to] = vertex;
                    parent_edge[to] = edge.id;
                    result.ord[to] = result.low[to] = timer++;
                    stack.push_back(to);
                } else if (result.ord[to] < result.low[vertex]) {
                    result.low[vertex] = result.ord[to];
                }
                continue;
            }

            stack.pop_back();
            const int parent_vertex = parent[vertex];
            if (parent_vertex == -1) continue;
            if (result.low[vertex] < result.low[parent_vertex]) {
                result.low[parent_vertex] = result.low[vertex];
            }
            if (result.ord[parent_vertex] < result.low[vertex]) {
                result.bridge[parent_edge[vertex]] = true;
            }
        }
    }

    for (int root = 0; root < n; root++) {
        if (result.component_of_vertex[root] != -1) continue;
        const int component = result.component_count();
        result.components.emplace_back();
        result.component_of_vertex[root] = component;
        stack.push_back(root);
        while (!stack.empty()) {
            const int vertex = stack.back();
            stack.pop_back();
            result.components.back().push_back(vertex);
            for (const Edge<T>& edge : graph[vertex]) {
                if (!edge.alive || result.bridge[edge.id]) continue;
                if (result.component_of_vertex[edge.to] != -1) continue;
                result.component_of_vertex[edge.to] = component;
                stack.push_back(edge.to);
            }
        }
    }

    for (int edge_id = 0; edge_id < edge_count; edge_id++) {
        if (!result.bridge[edge_id]) continue;
        result.bridge_ids.push_back(edge_id);
        const int first_component = result.component_of_vertex[edge_from[edge_id]];
        const int second_component = result.component_of_vertex[edge_to[edge_id]];
        assert(first_component != second_component);
        result.bridge_forest_edges.push_back(
            TwoEdgeConnectedBridge{first_component, second_component, edge_id});
    }
    return result;
}

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_TWO_EDGE_CONNECTED_COMPONENTS_HPP

#line 1 "graph/two_edge_connected_components.hpp"



#include <cassert>
#include <vector>

#line 1 "graph/graph.hpp"



#include <array>
#line 6 "graph/graph.hpp"
#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 8 "graph/two_edge_connected_components.hpp"

namespace m1une {
namespace graph {

struct TwoEdgeConnectedBridge {
    int from;
    int to;
    int edge_id;
};

struct TwoEdgeConnectedComponentsResult {
    std::vector<std::vector<int>> components;
    std::vector<int> component_of_vertex;
    std::vector<int> bridge_ids;
    std::vector<char> bridge;
    std::vector<TwoEdgeConnectedBridge> bridge_forest_edges;
    std::vector<int> ord;
    std::vector<int> low;

    int component_count() const {
        return int(components.size());
    }

    bool same(int first, int second) const {
        assert(0 <= first && first < int(component_of_vertex.size()));
        assert(0 <= second && second < int(component_of_vertex.size()));
        return component_of_vertex[first] == component_of_vertex[second];
    }

    bool is_bridge(int edge_id) const {
        assert(0 <= edge_id && edge_id < int(bridge.size()));
        return bridge[edge_id];
    }
};

// Removes every active bridge and returns the remaining connected components.
// The first lowlink traversal and the component traversal are both iterative.
template <class T>
TwoEdgeConnectedComponentsResult two_edge_connected_components(
    const Graph<T>& graph
) {
    const int n = graph.size();
    const int edge_count = graph.edge_count();

    TwoEdgeConnectedComponentsResult result;
    result.component_of_vertex.assign(n, -1);
    result.bridge.assign(edge_count, false);
    result.ord.assign(n, -1);
    result.low.assign(n, -1);

    std::vector<int> edge_from(edge_count, -1);
    std::vector<int> edge_to(edge_count, -1);
    std::vector<int> incidence_count(edge_count, 0);
    for (int vertex = 0; vertex < n; vertex++) {
        for (const Edge<T>& edge : graph[vertex]) {
            if (!edge.alive) continue;
            assert(0 <= edge.id && edge.id < edge_count);
            if (incidence_count[edge.id] == 0) {
                edge_from[edge.id] = edge.from;
                edge_to[edge.id] = edge.to;
            }
            incidence_count[edge.id]++;
        }
    }
#ifndef NDEBUG
    for (int edge_id = 0; edge_id < edge_count; edge_id++) {
        if (incidence_count[edge_id] != 0) assert(incidence_count[edge_id] == 2);
    }
#endif

    std::vector<int> parent(n, -1);
    std::vector<int> parent_edge(n, -1);
    std::vector<int> next_edge(n, 0);
    std::vector<int> stack;
    int timer = 0;

    for (int root = 0; root < n; root++) {
        if (result.ord[root] != -1) continue;
        result.ord[root] = result.low[root] = timer++;
        stack.push_back(root);
        while (!stack.empty()) {
            const int vertex = stack.back();
            if (next_edge[vertex] < int(graph[vertex].size())) {
                const Edge<T>& edge = graph[vertex][next_edge[vertex]++];
                if (!edge.alive || edge.id == parent_edge[vertex]) continue;
                const int to = edge.to;
                if (result.ord[to] == -1) {
                    parent[to] = vertex;
                    parent_edge[to] = edge.id;
                    result.ord[to] = result.low[to] = timer++;
                    stack.push_back(to);
                } else if (result.ord[to] < result.low[vertex]) {
                    result.low[vertex] = result.ord[to];
                }
                continue;
            }

            stack.pop_back();
            const int parent_vertex = parent[vertex];
            if (parent_vertex == -1) continue;
            if (result.low[vertex] < result.low[parent_vertex]) {
                result.low[parent_vertex] = result.low[vertex];
            }
            if (result.ord[parent_vertex] < result.low[vertex]) {
                result.bridge[parent_edge[vertex]] = true;
            }
        }
    }

    for (int root = 0; root < n; root++) {
        if (result.component_of_vertex[root] != -1) continue;
        const int component = result.component_count();
        result.components.emplace_back();
        result.component_of_vertex[root] = component;
        stack.push_back(root);
        while (!stack.empty()) {
            const int vertex = stack.back();
            stack.pop_back();
            result.components.back().push_back(vertex);
            for (const Edge<T>& edge : graph[vertex]) {
                if (!edge.alive || result.bridge[edge.id]) continue;
                if (result.component_of_vertex[edge.to] != -1) continue;
                result.component_of_vertex[edge.to] = component;
                stack.push_back(edge.to);
            }
        }
    }

    for (int edge_id = 0; edge_id < edge_count; edge_id++) {
        if (!result.bridge[edge_id]) continue;
        result.bridge_ids.push_back(edge_id);
        const int first_component = result.component_of_vertex[edge_from[edge_id]];
        const int second_component = result.component_of_vertex[edge_to[edge_id]];
        assert(first_component != second_component);
        result.bridge_forest_edges.push_back(
            TwoEdgeConnectedBridge{first_component, second_component, edge_id});
    }
    return result;
}

}  // namespace graph
}  // namespace m1une

m1une's library

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

Two-Edge-Connected Components
(graph/two_edge_connected_components.hpp)

Overview

Graph Requirements

API

Example

Depends on

Required by

Verified with

Code

Two-Edge-Connected Components (graph/two_edge_connected_components.hpp)

Overview

Graph Requirements

API

Example

Depends on

Required by

Verified with

Code

Two-Edge-Connected Components
(graph/two_edge_connected_components.hpp)