complement_graph_components.hpp¶
Connected components of the complement of an undirected graph.
Verified by connected_components_of_complement_graph.
在线性对数级复杂度内求补图的连通分量，而不显式建立所有补边。
Implementation¶
#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 <list>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
/// @brief Connected components of the complement of an undirected graph.
inline std::vector<std::vector<int>>
complement_graph_components(int vertex_count,
const std::vector<std::pair<int, int>> &edges) {
assert(vertex_count >= 0);
std::vector<std::vector<int>> graph(vertex_count);
for (auto [first, second] : edges) {
assert(0 <= first && first < vertex_count);
assert(0 <= second && second < vertex_count);
graph[first].push_back(second);
graph[second].push_back(first);
}
std::list<int> unvisited;
for (int vertex = 0; vertex < vertex_count; vertex++) {
unvisited.push_back(vertex);
}
std::vector<int> neighbor_stamp(vertex_count);
int stamp = 0;
std::vector<std::vector<int>> components;
while (!unvisited.empty()) {
int start = unvisited.front();
unvisited.pop_front();
components.push_back({start});
std::queue<int> queue;
queue.push(start);
while (!queue.empty()) {
int vertex = queue.front();
queue.pop();
++stamp;
for (int next : graph[vertex]) {
neighbor_stamp[next] = stamp;
}
for (auto iterator = unvisited.begin(); iterator != unvisited.end();) {
int candidate = *iterator;
if (neighbor_stamp[candidate] == stamp) {
++iterator;
} else {
components.back().push_back(candidate);
queue.push(candidate);
iterator = unvisited.erase(iterator);
}
}
}
}
return components;
}
} // namespace noya
#endif // NOYA_COMPLEMENT_GRAPH_COMPONENTS_HPP
#include <cassert>
#include <list>
#include <queue>
#include <utility>
#include <vector>
/// @complexity Time: O(V + E).
/// Space: O(V + E).
namespace noya {
/// @brief Connected components of the complement of an undirected graph.
inline std::vector<std::vector<int>>
complement_graph_components(int vertex_count,
const std::vector<std::pair<int, int>> &edges) {
assert(vertex_count >= 0);
std::vector<std::vector<int>> graph(vertex_count);
for (auto [first, second] : edges) {
assert(0 <= first && first < vertex_count);
assert(0 <= second && second < vertex_count);
graph[first].push_back(second);
graph[second].push_back(first);
}
std::list<int> unvisited;
for (int vertex = 0; vertex < vertex_count; vertex++) {
unvisited.push_back(vertex);
}
std::vector<int> neighbor_stamp(vertex_count);
int stamp = 0;
std::vector<std::vector<int>> components;
while (!unvisited.empty()) {
int start = unvisited.front();
unvisited.pop_front();
components.push_back({start});
std::queue<int> queue;
queue.push(start);
while (!queue.empty()) {
int vertex = queue.front();
queue.pop();
++stamp;
for (int next : graph[vertex]) {
neighbor_stamp[next] = stamp;
}
for (auto iterator = unvisited.begin(); iterator != unvisited.end();) {
int candidate = *iterator;
if (neighbor_stamp[candidate] == stamp) {
++iterator;
} else {
components.back().push_back(candidate);
queue.push(candidate);
iterator = unvisited.erase(iterator);
}
}
}
}
return components;
}
} // namespace noya