C++ Library for Competitive Programming
#include "emthrm/graph/connencted_component_of_complement_graph.hpp"
$O(\lvert V \rvert + \lvert E \rvert)$
名前 | 戻り値 |
---|---|
template <typename CostType> UnionFind connencted_component_of_complement_graph(const std::vector<std::vector<Edge<CostType>>>& graph);
|
無向グラフ $\mathrm{graph}$ の補グラフの連結成分分解 |
https://codeforces.com/contest/1242/submission/113385795
#ifndef EMTHRM_GRAPH_CONNENCTED_COMPONENT_OF_COMPLEMENT_GRAPH_HPP_
#define EMTHRM_GRAPH_CONNENCTED_COMPONENT_OF_COMPLEMENT_GRAPH_HPP_
#include <ranges>
#include <vector>
#include "emthrm/data_structure/union-find/union-find.hpp"
#include "emthrm/graph/edge.hpp"
namespace emthrm {
template <typename CostType>
UnionFind connencted_component_of_complement_graph(
const std::vector<std::vector<Edge<CostType>>>& graph) {
const int n = graph.size();
UnionFind union_find(n);
const auto check = [&graph, n, &union_find](const int ver) -> void {
std::vector<bool> is_adjacent(n, false);
for (const int e : graph[ver]
| std::views::transform(&Edge<CostType>::dst)) {
is_adjacent[e] = true;
}
for (int i = 0; i < n; ++i) {
if (!is_adjacent[i]) union_find.unite(ver, i);
}
};
int argmin_deg = 0;
for (int i = 1; i < n; ++i) {
if (graph[i].size() < graph[argmin_deg].size()) argmin_deg = i;
}
check(argmin_deg);
for (const int e : graph[argmin_deg]
| std::views::transform(&Edge<CostType>::dst)) {
check(e);
}
return union_find;
}
} // namespace emthrm
#endif // EMTHRM_GRAPH_CONNENCTED_COMPONENT_OF_COMPLEMENT_GRAPH_HPP_
#line 1 "include/emthrm/graph/connencted_component_of_complement_graph.hpp"
#include <ranges>
#include <vector>
#line 1 "include/emthrm/data_structure/union-find/union-find.hpp"
#include <utility>
#line 6 "include/emthrm/data_structure/union-find/union-find.hpp"
namespace emthrm {
struct UnionFind {
explicit UnionFind(const int n) : data(n, -1) {}
int root(const int ver) {
return data[ver] < 0 ? ver : data[ver] = root(data[ver]);
}
bool unite(int u, int v) {
u = root(u);
v = root(v);
if (u == v) return false;
if (data[u] > data[v]) std::swap(u, v);
data[u] += data[v];
data[v] = u;
return true;
}
bool is_same(const int u, const int v) { return root(u) == root(v); }
int size(const int ver) { return -data[root(ver)]; }
private:
std::vector<int> data;
};
} // 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 9 "include/emthrm/graph/connencted_component_of_complement_graph.hpp"
namespace emthrm {
template <typename CostType>
UnionFind connencted_component_of_complement_graph(
const std::vector<std::vector<Edge<CostType>>>& graph) {
const int n = graph.size();
UnionFind union_find(n);
const auto check = [&graph, n, &union_find](const int ver) -> void {
std::vector<bool> is_adjacent(n, false);
for (const int e : graph[ver]
| std::views::transform(&Edge<CostType>::dst)) {
is_adjacent[e] = true;
}
for (int i = 0; i < n; ++i) {
if (!is_adjacent[i]) union_find.unite(ver, i);
}
};
int argmin_deg = 0;
for (int i = 1; i < n; ++i) {
if (graph[i].size() < graph[argmin_deg].size()) argmin_deg = i;
}
check(argmin_deg);
for (const int e : graph[argmin_deg]
| std::views::transform(&Edge<CostType>::dst)) {
check(e);
}
return union_find;
}
} // namespace emthrm