橋の検出
(include/emthrm/graph/enumerate_bridges.hpp)

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

時間計算量

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

仕様

名前	戻り値
template <typename CostType> std::vector<Edge<CostType>> enumerate_bridges(const std::vector<std::vector<Edge<CostType>>>& graph);	無向グラフ $\mathrm{graph}$ の橋

参考文献

• https://www.slideshare.net/chokudai/arc039

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/GRL_3_B/review/4082847/emthrm/C++14

Depends on

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

Required by

• 二重辺連結成分 (2-edge-connected component) 分解 いもす法版 (include/emthrm/graph/2-edge-connected_components_by_imos.hpp)

Verified with

• グラフ/二重辺連結成分分解 いもす法版 (test/graph/2-edge-connected_components_by_imos.test.cpp)
• グラフ/橋の列挙 (test/graph/enumerate_bridges.test.cpp)

Code

#ifndef EMTHRM_GRAPH_ENUMERATE_BRIDGES_HPP_
#define EMTHRM_GRAPH_ENUMERATE_BRIDGES_HPP_

#include <algorithm>
#include <vector>

#include "emthrm/graph/edge.hpp"

namespace emthrm {

template <typename CostType>
std::vector<Edge<CostType>> enumerate_bridges(
    const std::vector<std::vector<Edge<CostType>>>& graph) {
  const int n = graph.size();
  std::vector<Edge<CostType>> res;
  std::vector<int> depth(n, -1), imos(n, 0);
  const auto dfs = [&graph, &res, &depth, &imos](
      auto dfs, const int par, const int ver) -> void {
    bool has_multiple_edges = false;
    for (const Edge<CostType>& e : graph[ver]) {
      if (depth[e.dst] == -1) {
        depth[e.dst] = depth[ver] + 1;
        dfs(dfs, ver, e.dst);
        if (imos[e.dst] == 0) {
          res.emplace_back(std::min(ver, e.dst), std::max(ver, e.dst), e.cost);
        }
        imos[ver] += imos[e.dst];
      } else if (!has_multiple_edges && e.dst == par) {
        has_multiple_edges = true;
      } else if (depth[e.dst] < depth[ver]) {
        ++imos[ver];
        --imos[e.dst];
      }
    }
  };
  for (int i = 0; i < n; ++i) {
    if (depth[i] == -1) {
      depth[i] = 0;
      dfs(dfs, -1, i);
    }
  }
  return res;
}

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_ENUMERATE_BRIDGES_HPP_

#line 1 "include/emthrm/graph/enumerate_bridges.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/enumerate_bridges.hpp"

namespace emthrm {

template <typename CostType>
std::vector<Edge<CostType>> enumerate_bridges(
    const std::vector<std::vector<Edge<CostType>>>& graph) {
  const int n = graph.size();
  std::vector<Edge<CostType>> res;
  std::vector<int> depth(n, -1), imos(n, 0);
  const auto dfs = [&graph, &res, &depth, &imos](
      auto dfs, const int par, const int ver) -> void {
    bool has_multiple_edges = false;
    for (const Edge<CostType>& e : graph[ver]) {
      if (depth[e.dst] == -1) {
        depth[e.dst] = depth[ver] + 1;
        dfs(dfs, ver, e.dst);
        if (imos[e.dst] == 0) {
          res.emplace_back(std::min(ver, e.dst), std::max(ver, e.dst), e.cost);
        }
        imos[ver] += imos[e.dst];
      } else if (!has_multiple_edges && e.dst == par) {
        has_multiple_edges = true;
      } else if (depth[e.dst] < depth[ver]) {
        ++imos[ver];
        --imos[e.dst];
      }
    }
  };
  for (int i = 0; i < n; ++i) {
    if (depth[i] == -1) {
      depth[i] = 0;
      dfs(dfs, -1, i);
    }
  }
  return res;
}

}  // namespace emthrm

Back to top page