graph/two_edge_connected_components.hpp

• View this file on GitHub
• Last update: 2025-06-19 13:38:46+09:00
• Include: #include "graph/two_edge_connected_components.hpp"

Depends on

• graph/lowlink.hpp

Verified with

• verify/yosupo_graph/graph_two_edge_connected_components.test.cpp

Code

#ifndef KK2_GRAPH_TWO_EDGE_CONNECTED_COMPONENTS_HPP
#define KK2_GRAPH_TWO_EDGE_CONNECTED_COMPONENTS_HPP 1

#include <vector>

#include "lowlink.hpp"

namespace kk2 {

template <class G> struct TwoEdgeConnectedComponents : LowLink<G> {
    TwoEdgeConnectedComponents(const G &g_) : LowLink<G>(g_) { init_tecc(); }

    std::vector<int> comp;
    std::vector<std::vector<int>> group;
    G forest;

    int size() const { return group.size(); }

  private:
    void init_tecc() {
        comp.resize(this->n, -1);
        int k = 0;
        auto dfs = [&](auto self, int now, int par) -> void {
            if (par != -1 && this->ord[par] >= this->low[now]) comp[now] = comp[par];
            else comp[now] = k++;

            for (auto &&e : this->g[now])
                if (comp[e.to] == -1) self(self, e.to, now);
        };
        for (int i = 0; i < this->n; i++)
            if (this->root[i]) dfs(dfs, i, -1);

        group.resize(k);
        for (int i = 0; i < this->n; i++) { group[comp[i]].emplace_back(i); }

        typename G::edge_collection tmp(this->bridges.size());
        for (int i = 0; i < (int)this->bridges.size(); i++) {
            tmp[i] = this->g.edges[this->bridges[i]];
            tmp[i].from = comp[tmp[i].from];
            tmp[i].to = comp[tmp[i].to];
            tmp[i].id = i;
        }
        forest = G(k, tmp);
    }
};

} // namespace kk2

#endif // KK2_GRAPH_TWO_EDGE_CONNECTED_COMPONENTS_HPP

#line 1 "graph/two_edge_connected_components.hpp"



#include <vector>

#line 1 "graph/lowlink.hpp"



#include <algorithm>
#include <cassert>
#include <functional>
#include <type_traits>
#line 9 "graph/lowlink.hpp"

namespace kk2 {

template <class G> struct LowLink {
    static_assert(!G::directed, "LowLink requires undirected graph");

    int n, m;
    const G &g;
    std::vector<int> ord, low;
    std::vector<bool> root, used_on_dfs_tree;
    std::vector<int> bridges, articulations;

    LowLink(const G &g_)
        : n(g_.num_vertices()),
          m(g_.num_edges()),
          g(g_),
          ord(n, -1),
          low(n, -1),
          root(n, false),
          used_on_dfs_tree(m, false) {
        init();
    }

  private:
    // v is a child of u in DFS tree
    // edge(u, v) is a bridge <=> ord[u] < low[v]

    // u is an articulation point <=> (u is root and u has two or more children) or
    // there exists a v which is a child of u in DFS tree and ord[u] <= low[v]

    void init() {
        int k = 0;
        auto dfs = [&](auto self, int u, int ei = -1) -> int {
            low[u] = ord[u] = k++;
            bool is_articulation = false;
            int count = 0;
            for (auto &&e : g[u]) {
                if (e.id == ei) continue;
                if (ord[e.to] == -1) {
                    ++count;
                    used_on_dfs_tree[e.id] = true;
                    low[u] = std::min(low[u], self(self, e.to, e.id));
                    if (ei != -1 and ord[u] <= low[e.to]) is_articulation = true;
                    if (ord[u] < low[e.to]) bridges.emplace_back(e.id);
                }
                // back edge
                else if (ord[e.to] < ord[u]) {
                    low[u] = std::min(low[u], ord[e.to]);
                }
            }
            if (ei == -1 and count >= 2) is_articulation = true;
            if (is_articulation) articulations.emplace_back(u);
            return low[u];
        };
        for (int u = 0; u < n; u++)
            if (ord[u] == -1) {
                dfs(dfs, u);
                root[u] = true;
            }
    }
};

} // namespace kk2


#line 7 "graph/two_edge_connected_components.hpp"

namespace kk2 {

template <class G> struct TwoEdgeConnectedComponents : LowLink<G> {
    TwoEdgeConnectedComponents(const G &g_) : LowLink<G>(g_) { init_tecc(); }

    std::vector<int> comp;
    std::vector<std::vector<int>> group;
    G forest;

    int size() const { return group.size(); }

  private:
    void init_tecc() {
        comp.resize(this->n, -1);
        int k = 0;
        auto dfs = [&](auto self, int now, int par) -> void {
            if (par != -1 && this->ord[par] >= this->low[now]) comp[now] = comp[par];
            else comp[now] = k++;

            for (auto &&e : this->g[now])
                if (comp[e.to] == -1) self(self, e.to, now);
        };
        for (int i = 0; i < this->n; i++)
            if (this->root[i]) dfs(dfs, i, -1);

        group.resize(k);
        for (int i = 0; i < this->n; i++) { group[comp[i]].emplace_back(i); }

        typename G::edge_collection tmp(this->bridges.size());
        for (int i = 0; i < (int)this->bridges.size(); i++) {
            tmp[i] = this->g.edges[this->bridges[i]];
            tmp[i].from = comp[tmp[i].from];
            tmp[i].to = comp[tmp[i].to];
            tmp[i].id = i;
        }
        forest = G(k, tmp);
    }
};

} // namespace kk2

Back to top page