sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "graph/two_edge_connected_components.hpp"
二辺連結成分は,どの1本の辺を取り除いても連結であるような部分グラフである.つまり,橋を含まない部分グラフである.
二辺連結成分を縮約して得られるグラフは森になっている.
空間計算量: $O(V + E)$
vector<int> two_edge_connected_components(vector<vector<int>> G, Lowlink low)
縮約には強連結成分分解のファイルにあるcontract関数がそのまま使える.
contract
#pragma once #include <algorithm> #include <vector> #include "lowlink.hpp" std::vector<int> two_edge_connected_components( const std::vector<std::vector<int>>& G, const Lowlink& low) { int k = 0; std::vector<int> comp(G.size(), -1); auto dfs = [&](const auto& dfs, int u) -> void { comp[u] = k; for (int v : G[u]) { if (comp[v] == -1 && !low.is_bridge(u, v)) dfs(dfs, v); } }; for (int v = 0; v < (int)G.size(); ++v) { if (comp[v] == -1) { dfs(dfs, v); ++k; } } return comp; } std::vector<std::vector<int>> contract(const std::vector<std::vector<int>>& G, const std::vector<int>& comp) { const int n = *std::ranges::max_element(comp) + 1; std::vector<std::vector<int>> G2(n); for (int i = 0; i < (int)G.size(); ++i) { for (int j : G[i]) { if (comp[i] != comp[j]) { G2[comp[i]].push_back(comp[j]); } } } for (int i = 0; i < n; ++i) { std::ranges::sort(G2[i]); G2[i].erase(std::ranges::unique(G2[i]).begin(), G2[i].end()); } return G2; }
#line 2 "graph/two_edge_connected_components.hpp" #include <algorithm> #include <vector> #line 3 "graph/lowlink.hpp" #include <utility> #line 5 "graph/lowlink.hpp" class Lowlink { public: std::vector<int> ord, low; std::vector<std::pair<int, int>> bridge; std::vector<int> articulation; Lowlink() = default; explicit Lowlink(const std::vector<std::vector<int>>& G) : ord(G.size(), -1), low(G.size()), G(G) { for (int i = 0; i < (int)G.size(); ++i) { if (ord[i] == -1) dfs(i, -1); } } bool is_bridge(int u, int v) const { if (ord[u] > ord[v]) std::swap(u, v); return ord[u] < low[v]; } private: std::vector<std::vector<int>> G; int k = 0; void dfs(int v, int p) { ord[v] = k++; low[v] = ord[v]; bool is_articulation = false, checked = false; int cnt = 0; for (int c : G[v]) { if (c == p && !checked) { checked = true; continue; } if (ord[c] == -1) { ++cnt; dfs(c, v); low[v] = std::min(low[v], low[c]); if (p != -1 && ord[v] <= low[c]) is_articulation = true; if (ord[v] < low[c]) bridge.push_back(std::minmax(v, c)); } else { low[v] = std::min(low[v], ord[c]); } } if (p == -1 && cnt > 1) is_articulation = true; if (is_articulation) articulation.push_back(v); } }; #line 6 "graph/two_edge_connected_components.hpp" std::vector<int> two_edge_connected_components( const std::vector<std::vector<int>>& G, const Lowlink& low) { int k = 0; std::vector<int> comp(G.size(), -1); auto dfs = [&](const auto& dfs, int u) -> void { comp[u] = k; for (int v : G[u]) { if (comp[v] == -1 && !low.is_bridge(u, v)) dfs(dfs, v); } }; for (int v = 0; v < (int)G.size(); ++v) { if (comp[v] == -1) { dfs(dfs, v); ++k; } } return comp; } std::vector<std::vector<int>> contract(const std::vector<std::vector<int>>& G, const std::vector<int>& comp) { const int n = *std::ranges::max_element(comp) + 1; std::vector<std::vector<int>> G2(n); for (int i = 0; i < (int)G.size(); ++i) { for (int j : G[i]) { if (comp[i] != comp[j]) { G2[comp[i]].push_back(comp[j]); } } } for (int i = 0; i < n; ++i) { std::ranges::sort(G2[i]); G2[i].erase(std::ranges::unique(G2[i]).begin(), G2[i].end()); } return G2; }