lowlink
(include/emthrm/graph/lowlink.hpp)

View this file on GitHub
Last update: 2023-02-24 21:17:22+09:00
Include: #include "emthrm/graph/lowlink.hpp"

深さ優先探索木 (depth-first search tree) で頂点 $i$ の訪問時刻を $\mathrm{order}_i$ とおく。このとき子孫から後退辺 (back edge) を高々一度通ることで到達できる頂点の $\mathrm{order}$ の最小値である。

橋 (bridge)

無向グラフ $G = (V, E)$ に対して、グラフ $(V, E \setminus \lbrace e \rbrace)$ が非連結となる辺 $e$ である。

関節点 (articulation point)

無向グラフ $G = (V, E)$ に対して、グラフ $(V \setminus \lbrace v \rbrace, E)$ が非連結となる頂点 $v$ である。

時間計算量

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

仕様

template <typename CostType>
struct Lowlink;

CostType：辺のコストを表す型

メンバ変数

名前	説明
`std::vector<int> order`	`order[i]` は頂点 $i$ の訪問時刻を表す。
`std::vector<int> lowlink`	lowlink
`std::vector<int> 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);`	無向グラフ $\mathrm{graph}$ に対してオブジェクトを構築する。

参考文献

http://kagamiz.hatenablog.com/entry/2013/10/05/005213

Submissons

Depends on

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

Required by

Verified with

Code

#ifndef EMTHRM_GRAPH_LOWLINK_HPP_
#define EMTHRM_GRAPH_LOWLINK_HPP_

#include <algorithm>
#include <vector>

#include "emthrm/graph/edge.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

#endif  // EMTHRM_GRAPH_LOWLINK_HPP_

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



#include <algorithm>
#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 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

lowlink (include/emthrm/graph/lowlink.hpp)