二重辺連結成分 (2-edge-connected component) 分解 lowlink 版
(include/emthrm/graph/2-edge-connected_components_by_lowlink.hpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Include: #include "emthrm/graph/2-edge-connected_components_by_lowlink.hpp"

二重辺連結成分 (2-edge-connected component) 分解

無向グラフを橋の存在しない部分グラフに分解することである。

それぞれの成分には、任意の3点を始点・経由点・終点とする辺素パスが存在し、さらに任意の2点を結ぶ2本以上の辺素パスが存在する。

bridge-block tree

二重辺連結成分を一つの頂点に縮約することで得られる木である。

時間計算量

	時間計算量
lowlink 版	$O(\lvert V \rvert + \lvert E \rvert)$
いもす法版	$O(\lvert V \rvert + \lvert E \rvert \log{\lvert E \rvert})$

仕様

lowlink 版

template <typename CostType, bool IS_FULL_VER = false>
struct TwoEdgeConnectedComponents : Lowlink<CostType>;

• CostType：辺のコストを表す型
• IS_FULL_VER：完全版かを表す変数

メンバ変数

名前	説明	要件
std::vector<int> id	id[i] は元のグラフの頂点 $i$ を含む頂点を表す。
std::vector<std::vector<int>> vertices	vertices[i] は縮約後のグラフの頂点 $i$ に含まれる頂点を表す。	完全版
std::vector<std::vector<Edge<CostType>>> g	二重辺連結成分を一つの頂点に縮約したグラフ

メンバ関数

名前	効果
explicit TwoEdgeConnectedComponents(const std::vector<std::vector<Edge<CostType>>>& graph);	無向グラフ $\mathrm{graph}$ に対してオブジェクトを構築する。

いもす法版

template <typename CostType, bool IS_FULL_VER = false>
struct TwoEdgeConnectedComponentsByImos;

• CostType：辺のコストを表す型
• IS_FULL_VER：完全版かを表す変数

メンバ変数

名前	説明	要件
std::vector<int> id	id[i] は元のグラフの頂点 $i$ を含む頂点を表す。
std::vector<Edge<CostType>> bridge	橋
std::vector<std::vector<int>> vertices	vertices[i] は縮約後のグラフの頂点 $i$ に含まれる頂点を表す。	完全版
std::vector<std::vector<Edge<CostType>>> g	二重辺連結成分を一つの頂点に縮約したグラフ

メンバ関数

名前	効果
explicit TwoEdgeConnectedComponentsByImos(const std::vector<std::vector<Edge<CostType>>>& graph);	無向グラフ $\mathrm{graph}$ に対してオブジェクトを構築する。

参考文献

• https://en.wikipedia.org/wiki/Bridge_(graph_theory)
• https://www.slideshare.net/chokudai/arc039

lowlink 版

• https://ei1333.github.io/luzhiled/snippets/graph/two-edge-connected-components.html

TODO

• 三重辺連結成分分解
  • https://ja.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E3%82%B0%E3%83%A9%E3%83%95
  • https://judge.yosupo.jp/problem/three_edge_connected_components

Submissons

• lowlink 版
• いもす法版

Depends on

• 辺 (include/emthrm/graph/edge.hpp)
• lowlink (include/emthrm/graph/lowlink.hpp)

Verified with

• グラフ/二重辺連結成分分解 lowlink 版 (test/graph/2-edge-connected_components_by_lowlink.test.cpp)

Code

#ifndef EMTHRM_GRAPH_2_EDGE_CONNECTED_COMPONENTS_BY_LOWLINK_HPP_
#define EMTHRM_GRAPH_2_EDGE_CONNECTED_COMPONENTS_BY_LOWLINK_HPP_

// #include <algorithm>
#include <ranges>
#include <vector>

#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/lowlink.hpp"

namespace emthrm {

template <typename CostType, bool IS_FULL_VER = false>
struct TwoEdgeConnectedComponents : Lowlink<CostType> {
  std::vector<int> id;
  std::vector<std::vector<int>> vertices;
  std::vector<std::vector<Edge<CostType>>> g;

  explicit TwoEdgeConnectedComponents(
      const std::vector<std::vector<Edge<CostType>>>& graph)
      : Lowlink<CostType>(graph) {
    const int n = graph.size();
    id.assign(n, -1);
    int m = 0;
    for (int i = 0; i < n; ++i) {
      if (id[i] == -1) dfs(-1, i, &m);
    }
    g.resize(m);
    for (const Edge<CostType>& e : this->bridges) {
      const int u = id[e.src], v = id[e.dst];
      g[u].emplace_back(u, v, e.cost);
      g[v].emplace_back(v, u, e.cost);
    }
    // if constexpr (IS_FULL_VER) {
    //   for (int i = 0; i < m; ++i) {
    //     std::sort(vertices[i].begin(), vertices[i].end());
    //   }
    // }
  }

 private:
  void dfs(const int par, const int ver, int* m) {
    if (par != -1 && this->order[par] >= this->lowlink[ver]) {
      id[ver] = id[par];
    } else {
      id[ver] = (*m)++;
      if constexpr (IS_FULL_VER) vertices.emplace_back();
    }
    if constexpr (IS_FULL_VER) vertices[id[ver]].emplace_back(ver);
    for (const int e : this->graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (id[e] == -1) dfs(ver, e, m);
    }
  }
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_2_EDGE_CONNECTED_COMPONENTS_BY_LOWLINK_HPP_

#line 1 "include/emthrm/graph/2-edge-connected_components_by_lowlink.hpp"



// #include <algorithm>
#include <ranges>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/graph/lowlink.hpp"



#include <algorithm>
#line 6 "include/emthrm/graph/lowlink.hpp"

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 8 "include/emthrm/graph/lowlink.hpp"

namespace emthrm {

template <typename CostType>
struct Lowlink {
  std::vector<int> order, lowlink, articulation_points;
  std::vector<Edge<CostType>> bridges;
  const std::vector<std::vector<Edge<CostType>>> graph;

  explicit Lowlink(const std::vector<std::vector<Edge<CostType>>>& graph)
      : graph(graph) {
    const int n = graph.size();
    order.assign(n, -1);
    lowlink.resize(n);
    int t = 0;
    for (int i = 0; i < n; ++i) {
      if (order[i] == -1) dfs(-1, i, &t);
    }
  }

 private:
  void dfs(const int par, const int ver, int* t) {
    order[ver] = lowlink[ver] = (*t)++;
    int num = 0;
    bool is_articulation_point = false;
    for (const Edge<CostType>& e : graph[ver]) {
      if (order[e.dst] == -1) {
        ++num;
        dfs(ver, e.dst, t);
        lowlink[ver] = std::min(lowlink[ver], lowlink[e.dst]);
        if (order[ver] <= lowlink[e.dst]) {
          is_articulation_point = true;
          if (order[ver] < lowlink[e.dst]) {
            bridges.emplace_back(std::min(ver, e.dst), std::max(ver, e.dst),
                                 e.cost);
          }
        }
      } else if (e.dst != par) {
        lowlink[ver] = std::min(lowlink[ver], order[e.dst]);
      }
    }
    if ((par == -1 && num >= 2) || (par != -1 && is_articulation_point)) {
      articulation_points.emplace_back(ver);
    }
  }
};

}  // namespace emthrm


#line 10 "include/emthrm/graph/2-edge-connected_components_by_lowlink.hpp"

namespace emthrm {

template <typename CostType, bool IS_FULL_VER = false>
struct TwoEdgeConnectedComponents : Lowlink<CostType> {
  std::vector<int> id;
  std::vector<std::vector<int>> vertices;
  std::vector<std::vector<Edge<CostType>>> g;

  explicit TwoEdgeConnectedComponents(
      const std::vector<std::vector<Edge<CostType>>>& graph)
      : Lowlink<CostType>(graph) {
    const int n = graph.size();
    id.assign(n, -1);
    int m = 0;
    for (int i = 0; i < n; ++i) {
      if (id[i] == -1) dfs(-1, i, &m);
    }
    g.resize(m);
    for (const Edge<CostType>& e : this->bridges) {
      const int u = id[e.src], v = id[e.dst];
      g[u].emplace_back(u, v, e.cost);
      g[v].emplace_back(v, u, e.cost);
    }
    // if constexpr (IS_FULL_VER) {
    //   for (int i = 0; i < m; ++i) {
    //     std::sort(vertices[i].begin(), vertices[i].end());
    //   }
    // }
  }

 private:
  void dfs(const int par, const int ver, int* m) {
    if (par != -1 && this->order[par] >= this->lowlink[ver]) {
      id[ver] = id[par];
    } else {
      id[ver] = (*m)++;
      if constexpr (IS_FULL_VER) vertices.emplace_back();
    }
    if constexpr (IS_FULL_VER) vertices[id[ver]].emplace_back(ver);
    for (const int e : this->graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (id[e] == -1) dfs(ver, e, m);
    }
  }
};

}  // namespace emthrm

Back to top page