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

View this file on GitHub
Last update: 2023-02-25 16:35:06+09:00
Problem: https://judge.yosupo.jp/problem/two_edge_connected_components

Depends on

Code

/*
 * @title グラフ/二重辺連結成分分解 いもす法版
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/two_edge_connected_components
 */

#include <iostream>
#include <vector>

#include "emthrm/graph/2-edge-connected_components_by_imos.hpp"
#include "emthrm/graph/edge.hpp"

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<emthrm::Edge<bool>>> graph(n);
  while (m--) {
    int a, b;
    std::cin >> a >> b;
    graph[a].emplace_back(a, b);
    graph[b].emplace_back(b, a);
  }
  const std::vector<std::vector<int>> ans =
      emthrm::TwoEdgeConnectedComponentsByImos<bool, true>(graph).vertices;
  const int k = ans.size();
  std::cout << k << '\n';
  for (int i = 0; i < k; ++i) {
    const int l = ans[i].size();
    std::cout << l << ' ';
    for (int j = 0; j < l; ++j) {
      std::cout << ans[i][j] << " \n"[j + 1 == l];
    }
  }
  return 0;
}

#line 1 "test/graph/2-edge-connected_components_by_imos.test.cpp"
/*
 * @title グラフ/二重辺連結成分分解 いもす法版
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/two_edge_connected_components
 */

#include <iostream>
#include <vector>

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



#include <algorithm>
#include <set>
#include <queue>
#include <ranges>
#include <utility>
#line 10 "include/emthrm/graph/2-edge-connected_components_by_imos.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 1 "include/emthrm/graph/enumerate_bridges.hpp"



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


#line 13 "include/emthrm/graph/2-edge-connected_components_by_imos.hpp"

namespace emthrm {

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

  explicit TwoEdgeConnectedComponentsByImos(
      const std::vector<std::vector<Edge<CostType>>>& graph)
      : bridge(enumerate_bridges(graph)) {
    const int n = graph.size();
    id.assign(n, -1);
    std::set<std::pair<int, int>> st;
    for (const Edge<CostType>& e : bridge) st.emplace(e.src, e.dst);
    int m = 0;
    std::queue<int> que;
    for (int i = 0; i < n; ++i) {
      if (id[i] != -1) continue;
      que.emplace(i);
      id[i] = m++;
      if constexpr (IS_FULL_VER) vertices.emplace_back(std::vector<int>{i});
      while (!que.empty()) {
        const int ver = que.front();
        que.pop();
        for (const int e : graph[ver]
                         | std::views::transform(&Edge<CostType>::dst)) {
          if (id[e] == -1 && !st.contains(std::minmax(ver, e))) {
            id[e] = id[i];
            if constexpr (IS_FULL_VER) vertices.back().emplace_back(e);
            que.emplace(e);
          }
        }
      }
    }
    g.resize(m);
    for (const Edge<CostType>& e : bridge) {
      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());
      }
    }
  }
};

}  // namespace emthrm


#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 12 "test/graph/2-edge-connected_components_by_imos.test.cpp"

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<emthrm::Edge<bool>>> graph(n);
  while (m--) {
    int a, b;
    std::cin >> a >> b;
    graph[a].emplace_back(a, b);
    graph[b].emplace_back(b, a);
  }
  const std::vector<std::vector<int>> ans =
      emthrm::TwoEdgeConnectedComponentsByImos<bool, true>(graph).vertices;
  const int k = ans.size();
  std::cout << k << '\n';
  for (int i = 0; i < k; ++i) {
    const int l = ans[i].size();
    std::cout << l << ' ';
    for (int j = 0; j < l; ++j) {
      std::cout << ans[i][j] << " \n"[j + 1 == l];
    }
  }
  return 0;
}

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

Depends on

Code

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