二重頂点連結成分 (biconnected component) 分解
(include/emthrm/graph/biconnected_component.hpp)

View this file on GitHub
Last update: 2023-05-12 15:57:02+09:00
Include: #include "emthrm/graph/biconnected_component.hpp"

無向グラフを関節点の存在しない辺集合に分割することである。

それぞれの成分には、任意の相異なる3点を始点・経由点・終点とする単純パスが存在する。

block-cut tree

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

カクタスグラフ (cactus)

任意の辺が高々一つの単純閉路に含まれる、すなわち任意の異なる単純閉路が高々一つの共通頂点をもつグラフである。

任意の二重頂点連結成分は橋または単純閉路となる。

e.g. 任意の閉路長が奇数となるグラフ

時間計算量

$O(\lvert V \rvert + \lvert E \rvert)$

完全版 $O(\lvert V \rvert \log{\lvert V \rvert} + \lvert E \rvert)$ ?

仕様

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

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

メンバ変数

名前	説明	要件
`std::vector<int> id`	`id[i]` は元のグラフの頂点 $i$ を含むブロックを表す。ただし関節点のときは $-1$ である。	完全版
`std::vector<std::vector<int>> vertices`	`vertices[i]` は縮約後のグラフのブロック $i$ に含まれる頂点を表す。	完全版
`std::vector<std::vector<int>> cutpoint`	`cutpoint[i]` は元のグラフの関節点 $i$ を含むブロックを表す。	完全版
`std::vector<std::vector<Edge<CostType>>> block`	`block[i]` は縮約後のグラフのブロック $i$ に含まれる辺を表す。

メンバ関数

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

参考文献

John Hopcroft and Robert Tarjan: Algorithm 447: efficient algorithms for graph manipulation, Communications of the ACM, Vol. 16, No. 6, pp. 372–378 (1973). https://doi.org/10.1145/362248.362272
~~https://www.learning-algorithms.com/entry/2018/03/21/152148~~
https://ei1333.github.io/luzhiled/snippets/graph/bi-connected-components.html
https://codeforces.com/blog/entry/14832

カクタスグラフ

https://pekempey.hatenablog.com/entry/2017/03/28/203856

TODO

https://judge.yosupo.jp/problem/biconnected_components

Submissons

https://atcoder.jp/contests/nadafes2022_day2/submissions/31595927

Depends on

Verified with

グラフ/二重頂点連結成分分解 (test/graph/biconnected_component.test.cpp)

Code

#ifndef EMTHRM_GRAPH_BICONNECTED_COMPONENT_HPP_
#define EMTHRM_GRAPH_BICONNECTED_COMPONENT_HPP_

// #include <algorithm>
#include <set>
#include <utility>
#include <vector>

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

namespace emthrm {

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

  explicit BiconnectedComponent(
      const std::vector<std::vector<Edge<CostType>>>& graph)
      : Lowlink<CostType>(graph) {
    const int n = graph.size();
    id.assign(n, -2);
    if constexpr (IS_FULL_VER) {
      cutpoint.resize(n);
      is_articulation_point.assign(n, false);
      for (const int articulation_point : this->articulation_points) {
        is_articulation_point[articulation_point] = true;
      }
    }
    for (int i = 0; i < n; ++i) {
      if (id[i] == -2) dfs(-1, i);
    }
    // const int m = vertices.size();
    // for (int i = 0; i < m; ++i) {
    //   std::sort(block[i].begin(), block[i].end());
    // }
    // if constexpr (IS_FULL_VER) {
    //   for (int i = 0; i < m; ++i) {
    //     std::sort(vertices[i].begin(), vertices[i].end());
    //   }
    //   for (int i = 0; i < n; ++i) {
    //     std::sort(cutpoint[i].begin(), cutpoint[i].end());
    //   }
    // }
  }

 private:
  std::vector<bool> is_articulation_point;
  std::vector<Edge<CostType>> tmp;

  void dfs(const int par, const int ver) {
    id[ver] = -1;
    for (const Edge<CostType>& e : this->graph[ver]) {
      if (e.dst == par) continue;
      int src = ver, dst = e.dst;
      if (src > dst) std::swap(src, dst);
      if (id[e.dst] == -2 || this->order[e.dst] < this->order[ver]) {
        tmp.emplace_back(src, dst, e.cost);
      }
      if (id[e.dst] == -2) {
        dfs(ver, e.dst);
        if (this->lowlink[e.dst] >= this->order[ver]) {
          const int idx = block.size();
          block.emplace_back();
          std::set<int> st;
          while (true) {
            const Edge<CostType> edge = tmp.back();
            tmp.pop_back();
            block.back().emplace_back(edge);
            if constexpr (IS_FULL_VER) {
              st.emplace(edge.src);
              st.emplace(edge.dst);
            }
            if (edge.src == src && edge.dst == dst) break;
          }
          if constexpr (IS_FULL_VER) {
            vertices.emplace_back();
            for (const int el : st) {
              vertices.back().emplace_back(el);
              if (is_articulation_point[el]) {
                cutpoint[el].emplace_back(idx);
              } else {
                id[el] = idx;
              }
            }
          }
        }
      }
    }
  }
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_BICONNECTED_COMPONENT_HPP_

#line 1 "include/emthrm/graph/biconnected_component.hpp"



// #include <algorithm>
#include <set>
#include <utility>
#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 11 "include/emthrm/graph/biconnected_component.hpp"

namespace emthrm {

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

  explicit BiconnectedComponent(
      const std::vector<std::vector<Edge<CostType>>>& graph)
      : Lowlink<CostType>(graph) {
    const int n = graph.size();
    id.assign(n, -2);
    if constexpr (IS_FULL_VER) {
      cutpoint.resize(n);
      is_articulation_point.assign(n, false);
      for (const int articulation_point : this->articulation_points) {
        is_articulation_point[articulation_point] = true;
      }
    }
    for (int i = 0; i < n; ++i) {
      if (id[i] == -2) dfs(-1, i);
    }
    // const int m = vertices.size();
    // for (int i = 0; i < m; ++i) {
    //   std::sort(block[i].begin(), block[i].end());
    // }
    // if constexpr (IS_FULL_VER) {
    //   for (int i = 0; i < m; ++i) {
    //     std::sort(vertices[i].begin(), vertices[i].end());
    //   }
    //   for (int i = 0; i < n; ++i) {
    //     std::sort(cutpoint[i].begin(), cutpoint[i].end());
    //   }
    // }
  }

 private:
  std::vector<bool> is_articulation_point;
  std::vector<Edge<CostType>> tmp;

  void dfs(const int par, const int ver) {
    id[ver] = -1;
    for (const Edge<CostType>& e : this->graph[ver]) {
      if (e.dst == par) continue;
      int src = ver, dst = e.dst;
      if (src > dst) std::swap(src, dst);
      if (id[e.dst] == -2 || this->order[e.dst] < this->order[ver]) {
        tmp.emplace_back(src, dst, e.cost);
      }
      if (id[e.dst] == -2) {
        dfs(ver, e.dst);
        if (this->lowlink[e.dst] >= this->order[ver]) {
          const int idx = block.size();
          block.emplace_back();
          std::set<int> st;
          while (true) {
            const Edge<CostType> edge = tmp.back();
            tmp.pop_back();
            block.back().emplace_back(edge);
            if constexpr (IS_FULL_VER) {
              st.emplace(edge.src);
              st.emplace(edge.dst);
            }
            if (edge.src == src && edge.dst == dst) break;
          }
          if constexpr (IS_FULL_VER) {
            vertices.emplace_back();
            for (const int el : st) {
              vertices.back().emplace_back(el);
              if (is_articulation_point[el]) {
                cutpoint[el].emplace_back(idx);
              } else {
                id[el] = idx;
              }
            }
          }
        }
      }
    }
  }
};

}  // namespace emthrm

二重頂点連結成分 (biconnected component) 分解 (include/emthrm/graph/biconnected_component.hpp)