complement_graph_components.hpp¶
在线性复杂度内求补图的连通分量，不显式建立补边；保持按编号扫描的 BFS 顺序。
Complexity: Time: \(O(V + E)\). Space: \(O(V + E)\).
AC 记录：connected_components_of_complement_graph。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V + E).
/// Space: O(V + E).
#include <cassert>
#include <cstddef>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Connected components of the complement of an undirected graph.
/// Loops and duplicate edges are allowed; input is unchanged. Components start
/// at their smallest vertex and use BFS order with ascending candidate IDs.
inline std::vector<std::vector<int>>
complement_graph_components(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
if (n == 0) {
assert(es.empty());
return {};
}
std::vector<std::size_t> start(std::size_t(n) + 1);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a != b) {
++start[a];
++start[b];
}
}
for (int u = 0; u < n; u++) {
start[u + 1] += start[u];
}
std::vector<int> adj(start.back());
// Fill backwards: cumulative row ends become row starts in place.
for (auto [a, b] : es) {
if (a != b) {
adj[--start[a]] = b;
adj[--start[b]] = a;
}
}
std::vector<int> unv(n), mark(n, -1);
std::iota(unv.begin(), unv.end(), 0);
std::vector<std::vector<int>> components;
while (!unv.empty()) {
int s = unv.front();
unv.erase(unv.begin());
components.push_back({s});
auto &comp = components.back();
for (std::size_t head = 0; head < comp.size(); head++) {
if (unv.empty()) return components;
int u = comp[head];
for (auto i = start[u]; i < start[u + 1]; i++) {
mark[adj[i]] = u;
}
// Each retained candidate charges an original edge; each removal happens
// once. Root erasure costs no more than the following candidate scan.
int keep = 0;
for (int v : unv) {
if (mark[v] == u) {
unv[keep++] = v;
} else {
comp.push_back(v);
}
}
unv.resize(keep);
}
}
return components;
}
} // namespace noya
// NOYA_COMPLEMENT_GRAPH_COMPONENTS_HPP
#ifndef NOYA_COMPLEMENT_GRAPH_COMPONENTS_HPP
#define NOYA_COMPLEMENT_GRAPH_COMPONENTS_HPP 1
/// @complexity Time: O(V + E).
/// Space: O(V + E).
#include <cassert>
#include <cstddef>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Connected components of the complement of an undirected graph.
/// Loops and duplicate edges are allowed; input is unchanged. Components start
/// at their smallest vertex and use BFS order with ascending candidate IDs.
inline std::vector<std::vector<int>>
complement_graph_components(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
if (n == 0) {
assert(es.empty());
return {};
}
std::vector<std::size_t> start(std::size_t(n) + 1);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a != b) {
++start[a];
++start[b];
}
}
for (int u = 0; u < n; u++) {
start[u + 1] += start[u];
}
std::vector<int> adj(start.back());
// Fill backwards: cumulative row ends become row starts in place.
for (auto [a, b] : es) {
if (a != b) {
adj[--start[a]] = b;
adj[--start[b]] = a;
}
}
std::vector<int> unv(n), mark(n, -1);
std::iota(unv.begin(), unv.end(), 0);
std::vector<std::vector<int>> components;
while (!unv.empty()) {
int s = unv.front();
unv.erase(unv.begin());
components.push_back({s});
auto &comp = components.back();
for (std::size_t head = 0; head < comp.size(); head++) {
if (unv.empty()) return components;
int u = comp[head];
for (auto i = start[u]; i < start[u + 1]; i++) {
mark[adj[i]] = u;
}
// Each retained candidate charges an original edge; each removal happens
// once. Root erasure costs no more than the following candidate scan.
int keep = 0;
for (int v : unv) {
if (mark[v] == u) {
unv[keep++] = v;
} else {
comp.push_back(v);
}
}
unv.resize(keep);
}
}
return components;
}
} // namespace noya
#endif // NOYA_COMPLEMENT_GRAPH_COMPONENTS_HPP
/// @complexity Time: O(V + E).
/// Space: O(V + E).
#include <cassert>
#include <cstddef>
#include <numeric>
#include <utility>
#include <vector>
namespace noya {
/// @brief Connected components of the complement of an undirected graph.
/// Loops and duplicate edges are allowed; input is unchanged. Components start
/// at their smallest vertex and use BFS order with ascending candidate IDs.
inline std::vector<std::vector<int>>
complement_graph_components(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
if (n == 0) {
assert(es.empty());
return {};
}
std::vector<std::size_t> start(std::size_t(n) + 1);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a != b) {
++start[a];
++start[b];
}
}
for (int u = 0; u < n; u++) {
start[u + 1] += start[u];
}
std::vector<int> adj(start.back());
// Fill backwards: cumulative row ends become row starts in place.
for (auto [a, b] : es) {
if (a != b) {
adj[--start[a]] = b;
adj[--start[b]] = a;
}
}
std::vector<int> unv(n), mark(n, -1);
std::iota(unv.begin(), unv.end(), 0);
std::vector<std::vector<int>> components;
while (!unv.empty()) {
int s = unv.front();
unv.erase(unv.begin());
components.push_back({s});
auto &comp = components.back();
for (std::size_t head = 0; head < comp.size(); head++) {
if (unv.empty()) return components;
int u = comp[head];
for (auto i = start[u]; i < start[u + 1]; i++) {
mark[adj[i]] = u;
}
// Each retained candidate charges an original edge; each removal happens
// once. Root erasure costs no more than the following candidate scan.
int keep = 0;
for (int v : unv) {
if (mark[v] == u) {
unv[keep++] = v;
} else {
comp.push_back(v);
}
}
unv.resize(keep);
}
}
return components;
}
} // namespace noya
// NOYA_COMPLEMENT_GRAPH_COMPONENTS_HPP