C++ Library for Competitive Programming
/*
* @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;
}