C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title グラフ/二重頂点連結成分分解 * * verification-helper: IGNORE * verification-helper: PROBLEM https://atcoder.jp/contests/nadafes2022_day2/tasks/nadafes2022_day2_h */ #include <algorithm> #include <cassert> #include <iostream> #include <iterator> #include <set> #include <utility> #include <vector> #include "emthrm/graph/biconnected_component.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; --a; --b; graph[a].emplace_back(a, b); graph[b].emplace_back(b, a); } emthrm::BiconnectedComponent<bool, true> biconnected_component(graph); const int x = biconnected_component.articulation_points.size(); const int y = biconnected_component.vertices.size(); std::sort(biconnected_component.articulation_points.begin(), biconnected_component.articulation_points.end()); std::vector<std::vector<int>> block_cut_tree(x + y); std::vector<int> weight(x + y, 0); for (int i = 0; i < n; ++i) { if (biconnected_component.id[i] == -1) { const int index = std::distance(biconnected_component.articulation_points.begin(), std::lower_bound( biconnected_component.articulation_points.begin(), biconnected_component.articulation_points.end(), i)); for (const int block : biconnected_component.cutpoint[i]) { block_cut_tree[index].emplace_back(block + x); block_cut_tree[block + x].emplace_back(index); } ++weight[index]; } else { ++weight[biconnected_component.id[i] + x]; } } for (int i = 0; i < x + y; ++i) { std::sort(block_cut_tree[i].begin(), block_cut_tree[i].end()); block_cut_tree[i].erase( std::unique(block_cut_tree[i].begin(), block_cut_tree[i].end()), block_cut_tree[i].end()); } long long ans = static_cast<long long>(n) * (n - 1) / 2 * x; const auto dfs = [n, x, &block_cut_tree, &weight, &ans]( auto dfs, const int par, const int ver) -> int { int subtree = weight[ver]; if (ver < x) { for (const int e : block_cut_tree[ver]) { if (e != par) { const int child = dfs(dfs, ver, e); ans -= static_cast<long long>(child) * (child - 1) / 2 + child; subtree += child; } } ans -= static_cast<long long>(n - subtree) * (n - subtree - 1) / 2 + (n - subtree); } else { for (const int e : block_cut_tree[ver]) { if (e != par) subtree += dfs(dfs, ver, e); } } return subtree; }; assert(dfs(dfs, -1, 0) == n); std::cout << ans << '\n'; return 0; }
#line 1 "test/graph/biconnected_component.test.cpp" /* * @title グラフ/二重頂点連結成分分解 * * verification-helper: IGNORE * verification-helper: PROBLEM https://atcoder.jp/contests/nadafes2022_day2/tasks/nadafes2022_day2_h */ #include <algorithm> #include <cassert> #include <iostream> #include <iterator> #include <set> #include <utility> #include <vector> #line 1 "include/emthrm/graph/biconnected_component.hpp" // #include <algorithm> #line 8 "include/emthrm/graph/biconnected_component.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/lowlink.hpp" #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 #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 18 "test/graph/biconnected_component.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; --a; --b; graph[a].emplace_back(a, b); graph[b].emplace_back(b, a); } emthrm::BiconnectedComponent<bool, true> biconnected_component(graph); const int x = biconnected_component.articulation_points.size(); const int y = biconnected_component.vertices.size(); std::sort(biconnected_component.articulation_points.begin(), biconnected_component.articulation_points.end()); std::vector<std::vector<int>> block_cut_tree(x + y); std::vector<int> weight(x + y, 0); for (int i = 0; i < n; ++i) { if (biconnected_component.id[i] == -1) { const int index = std::distance(biconnected_component.articulation_points.begin(), std::lower_bound( biconnected_component.articulation_points.begin(), biconnected_component.articulation_points.end(), i)); for (const int block : biconnected_component.cutpoint[i]) { block_cut_tree[index].emplace_back(block + x); block_cut_tree[block + x].emplace_back(index); } ++weight[index]; } else { ++weight[biconnected_component.id[i] + x]; } } for (int i = 0; i < x + y; ++i) { std::sort(block_cut_tree[i].begin(), block_cut_tree[i].end()); block_cut_tree[i].erase( std::unique(block_cut_tree[i].begin(), block_cut_tree[i].end()), block_cut_tree[i].end()); } long long ans = static_cast<long long>(n) * (n - 1) / 2 * x; const auto dfs = [n, x, &block_cut_tree, &weight, &ans]( auto dfs, const int par, const int ver) -> int { int subtree = weight[ver]; if (ver < x) { for (const int e : block_cut_tree[ver]) { if (e != par) { const int child = dfs(dfs, ver, e); ans -= static_cast<long long>(child) * (child - 1) / 2 + child; subtree += child; } } ans -= static_cast<long long>(n - subtree) * (n - subtree - 1) / 2 + (n - subtree); } else { for (const int e : block_cut_tree[ver]) { if (e != par) subtree += dfs(dfs, ver, e); } } return subtree; }; assert(dfs(dfs, -1, 0) == n); std::cout << ans << '\n'; return 0; }