Complement-Graph Connected Components
(graph/complement_connected_components.hpp)

• View this file on GitHub
• Last update: 2026-08-13 01:41:40+09:00
• Include: #include "graph/complement_connected_components.hpp"

Overview

complement_connected_components partitions the vertices into connected components of the complement graph. Two distinct vertices are adjacent in the complement exactly when they are not adjacent in the input graph.

The complement can have quadratically many edges. This implementation scans an intrusive list of unassigned vertices and never constructs those edges, keeping the running time and memory linear in the input size.

Graph Interpretation

Every active edge of Graph<T> is treated as an undirected edge, regardless of how it was inserted. Self-loops are ignored. Parallel edges are treated as one edge, so they do not change the result.

Edge costs are ignored. The graph is not mutated.

API

The function reuses ConnectedComponents, the result type of the ordinary connected_components function.

struct ConnectedComponents {
    int count;
    std::vector<int> comp;
    std::vector<std::vector<int>> groups;

    bool same(int first, int second) const;
};

template <class T>
ConnectedComponents complement_connected_components(const Graph<T>& graph);

Member or function	Description	Complexity
count	Number of complement-graph components.	$O(1)$
comp[v]	Component containing vertex v.	$O(1)$
groups[c]	Vertices in component c; their order is unspecified.	–
same(first, second)	Whether two vertices belong to the same complement-graph component.	$O(1)$
complement_connected_components(graph)	Computes the complete partition without building the complement.	$O(N+M)$ time and memory

For an empty graph, count is 0 and both vectors are empty.

Example

#include "graph/complement_connected_components.hpp"
#include "graph/graph.hpp"

#include <iostream>

int main() {
    m1une::graph::Graph<> graph(4);
    graph.add_edge(0, 1);
    graph.add_edge(0, 2);
    graph.add_edge(0, 3);

    auto result = m1une::graph::complement_connected_components(graph);
    std::cout << result.count << "\n";      // 2
    std::cout << result.same(1, 3) << "\n";  // 1
    std::cout << result.same(0, 1) << "\n";  // 0
}

Depends on

• DSU (Disjoint Set Union) (ds/dsu/dsu.hpp)
• Connected Components (graph/connected_components.hpp)
• Graph (graph/graph.hpp)

Required by

• Graph All (graph/all.hpp)
• Undirected Graph Algorithms (graph/undirected.hpp)

Verified with

• verify/graph/complement_connected_components.test.cpp
• verify/graph/cow_game.test.cpp
• verify/graph/graph_algorithms.test.cpp
• verify/graph/range_edge_graph.test.cpp

Code

#ifndef M1UNE_GRAPH_COMPLEMENT_CONNECTED_COMPONENTS_HPP
#define M1UNE_GRAPH_COMPLEMENT_CONNECTED_COMPONENTS_HPP 1

#include <queue>
#include <vector>

#include "connected_components.hpp"

namespace m1une {
namespace graph {

// Computes connected components after complementing the underlying simple
// undirected graph, without constructing the complement graph.
template <class T>
ConnectedComponents complement_connected_components(const Graph<T>& graph) {
    const int size = graph.size();
    std::vector<std::vector<int>> adjacency(size);
    for (const Edge<T>& edge : graph.edges()) {
        if (edge.from == edge.to) continue;
        adjacency[edge.from].push_back(edge.to);
        adjacency[edge.to].push_back(edge.from);
    }

    const int sentinel = size;
    std::vector<int> next(size + 1);
    std::vector<int> previous(size + 1);
    if (size == 0) {
        next[sentinel] = previous[sentinel] = sentinel;
    } else {
        next[sentinel] = 0;
        previous[sentinel] = size - 1;
        for (int vertex = 0; vertex < size; vertex++) {
            next[vertex] = (vertex + 1 == size ? sentinel : vertex + 1);
            previous[vertex] = (vertex == 0 ? sentinel : vertex - 1);
        }
    }

    auto erase = [&](int vertex) {
        next[previous[vertex]] = next[vertex];
        previous[next[vertex]] = previous[vertex];
    };

    ConnectedComponents result;
    result.comp.assign(size, -1);
    std::vector<int> neighbor_stamp(size, -1);
    std::queue<int> queue;

    while (next[sentinel] != sentinel) {
        const int root = next[sentinel];
        erase(root);
        const int component = int(result.groups.size());
        result.groups.emplace_back();
        result.groups.back().push_back(root);
        result.comp[root] = component;
        queue.push(root);

        while (!queue.empty()) {
            const int vertex = queue.front();
            queue.pop();
            for (int to : adjacency[vertex]) neighbor_stamp[to] = vertex;

            int candidate = next[sentinel];
            while (candidate != sentinel) {
                const int following = next[candidate];
                if (neighbor_stamp[candidate] != vertex) {
                    erase(candidate);
                    result.comp[candidate] = component;
                    result.groups.back().push_back(candidate);
                    queue.push(candidate);
                }
                candidate = following;
            }
        }
    }
    result.count = int(result.groups.size());
    return result;
}

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_COMPLEMENT_CONNECTED_COMPONENTS_HPP

#line 1 "graph/complement_connected_components.hpp"



#include <queue>
#include <vector>

#line 1 "graph/connected_components.hpp"



#include <cassert>
#line 6 "graph/connected_components.hpp"

#line 1 "ds/dsu/dsu.hpp"



#include <algorithm>
#include <numeric>
#include <utility>
#line 8 "ds/dsu/dsu.hpp"

namespace m1une {
namespace ds {

struct Dsu {
   private:
    int _n;
    // parent_or_size[i] is the parent of i if it's >= 0.
    // If it's < 0, then i is a root and -parent_or_size[i] is the size of the group.
    std::vector<int> parent_or_size;

    // Returns {new leader, absorbed leader}. The absorbed leader is -1 when
    // both vertices already belong to the same component.
    std::pair<int, int> merge_leaders(int a, int b) {
        int x = leader(a), y = leader(b);
        if (x == y) return {x, -1};
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return {x, y};
    }

   public:
    Dsu() : _n(0) {}
    explicit Dsu(int n) : _n(n), parent_or_size(n, -1) {}

    // Merges the group containing 'a' with the group containing 'b'.
    // Returns the leader of the merged group.
    int merge(int a, int b) {
        return merge_leaders(a, b).first;
    }

    // Invokes callback(new_leader, absorbed_leader) after an actual merge.
    // Returns the leader of the merged group.
    template <class Callback>
    int merge(int a, int b, Callback&& callback) {
        std::pair<int, int> merged = merge_leaders(a, b);
        if (merged.second != -1) callback(merged.first, merged.second);
        return merged.first;
    }

    // Returns true if 'a' and 'b' belong to the same group.
    bool same(int a, int b) {
        return leader(a) == leader(b);
    }

    // Returns the leader (representative) of the group containing 'a'.
    int leader(int a) {
        if (parent_or_size[a] < 0) return a;
        // Path compression
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    // Returns the size of the group containing 'a'.
    int size(int a) {
        return -parent_or_size[leader(a)];
    }

    // Returns a list of all groups, where each group is a vector of its elements.
    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }),
                     result.end());
        return result;
    }
};

}  // namespace ds
}  // namespace m1une


#line 1 "graph/graph.hpp"



#include <array>
#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


#line 9 "graph/connected_components.hpp"

namespace m1une {
namespace graph {

struct ConnectedComponents {
    int count;
    std::vector<int> comp;
    std::vector<std::vector<int>> groups;

    bool same(int u, int v) const {
        assert(0 <= u && u < int(comp.size()));
        assert(0 <= v && v < int(comp.size()));
        return comp[u] == comp[v];
    }
};

template <class T>
ConnectedComponents connected_components(const Graph<T>& g) {
    int n = g.size();
    m1une::ds::Dsu dsu(n);
    for (const auto& e : g.edges()) dsu.merge(e.from, e.to);

    ConnectedComponents result;
    result.comp.assign(n, 0);
    std::vector<int> leader_to_comp(n, -1);
    for (int v = 0; v < n; v++) {
        int leader = dsu.leader(v);
        if (leader_to_comp[leader] == -1) {
            leader_to_comp[leader] = int(result.groups.size());
            result.groups.push_back({});
        }
        int c = leader_to_comp[leader];
        result.comp[v] = c;
        result.groups[c].push_back(v);
    }
    result.count = int(result.groups.size());

    return result;
}

}  // namespace graph
}  // namespace m1une


#line 8 "graph/complement_connected_components.hpp"

namespace m1une {
namespace graph {

// Computes connected components after complementing the underlying simple
// undirected graph, without constructing the complement graph.
template <class T>
ConnectedComponents complement_connected_components(const Graph<T>& graph) {
    const int size = graph.size();
    std::vector<std::vector<int>> adjacency(size);
    for (const Edge<T>& edge : graph.edges()) {
        if (edge.from == edge.to) continue;
        adjacency[edge.from].push_back(edge.to);
        adjacency[edge.to].push_back(edge.from);
    }

    const int sentinel = size;
    std::vector<int> next(size + 1);
    std::vector<int> previous(size + 1);
    if (size == 0) {
        next[sentinel] = previous[sentinel] = sentinel;
    } else {
        next[sentinel] = 0;
        previous[sentinel] = size - 1;
        for (int vertex = 0; vertex < size; vertex++) {
            next[vertex] = (vertex + 1 == size ? sentinel : vertex + 1);
            previous[vertex] = (vertex == 0 ? sentinel : vertex - 1);
        }
    }

    auto erase = [&](int vertex) {
        next[previous[vertex]] = next[vertex];
        previous[next[vertex]] = previous[vertex];
    };

    ConnectedComponents result;
    result.comp.assign(size, -1);
    std::vector<int> neighbor_stamp(size, -1);
    std::queue<int> queue;

    while (next[sentinel] != sentinel) {
        const int root = next[sentinel];
        erase(root);
        const int component = int(result.groups.size());
        result.groups.emplace_back();
        result.groups.back().push_back(root);
        result.comp[root] = component;
        queue.push(root);

        while (!queue.empty()) {
            const int vertex = queue.front();
            queue.pop();
            for (int to : adjacency[vertex]) neighbor_stamp[to] = vertex;

            int candidate = next[sentinel];
            while (candidate != sentinel) {
                const int following = next[candidate];
                if (neighbor_stamp[candidate] != vertex) {
                    erase(candidate);
                    result.comp[candidate] = component;
                    result.groups.back().push_back(candidate);
                    queue.push(candidate);
                }
                candidate = following;
            }
        }
    }
    result.count = int(result.groups.size());
    return result;
}

}  // namespace graph
}  // namespace m1une

Back to top page