Offline Dynamic Connectivity
(ds/dynamic_connectivity/offline_dynamic_connectivity.hpp)

• View this file on GitHub
• Last update: 2026-07-11 19:52:35+09:00
• Include: #include "ds/dynamic_connectivity/offline_dynamic_connectivity.hpp"

Overview

OfflineDynamicConnectivity records edge insertions, edge deletions, and connectivity queries in chronological order, then answers every query together with solve().

Each edge lifetime is inserted into a segment tree over time. RollbackDsu traverses that tree, adding exactly the edges active at each query and restoring its previous state when leaving a segment. Segment-tree edge lists use one compact contiguous allocation instead of one allocation per node.

Parallel edges and self-loops are supported. Every insertion returns a distinct edge id, and deletion refers to that id.

Methods

Method	Description	Complexity
OfflineDynamicConnectivity()	Creates an empty graph.	O(1)
OfflineDynamicConnectivity(int n)	Creates n vertices.	O(1)
int size() const	Returns the number of vertices.	O(1)
int edge_count() const	Returns the number of inserted edge ids.	O(1)
int query_count() const	Returns the number of recorded queries.	O(1)
int operation_count() const	Returns the number of recorded operations.	O(1)
void reserve_edges(int count)	Reserves storage for inserted edges.	O(L) when reallocation occurs
void reserve_queries(int count)	Reserves storage for connectivity queries.	O(K) when reallocation occurs
bool edge_alive(int id) const	Returns whether edge id is active at the end of the log.	O(1)
int add_edge(int u, int v)	Records an insertion and returns its edge id.	Amortized O(1)
bool erase_edge(int id)	Records deletion of an active edge. Returns false if already erased.	O(1)
int add_query(int u, int v)	Records a query and returns its query id.	Amortized O(1)
vector<bool> solve() const	Returns answers in query-id order.	O((Q + L log Q) log N)

Here Q is the number of recorded operations and L is the number of inserted edges. The segment-tree storage uses O(Q + L log Q) memory. The extra log N factor comes from rollback DSU leaders, which use union by size without path compression.

Calling solve() does not modify the recorded log, so it may be called again. More operations can also be appended afterward and solved as a longer log.

Example

#include "ds/dynamic_connectivity/offline_dynamic_connectivity.hpp"
#include <iostream>

int main() {
    m1une::ds::OfflineDynamicConnectivity graph(3);
    int e01 = graph.add_edge(0, 1);
    int first = graph.add_query(0, 2);
    int e12 = graph.add_edge(1, 2);
    int second = graph.add_query(0, 2);
    graph.erase_edge(e01);
    int third = graph.add_query(0, 2);

    std::vector<bool> answer = graph.solve();
    std::cout << answer[first] << '\n';   // 0
    std::cout << answer[second] << '\n';  // 1
    std::cout << answer[third] << '\n';   // 0

    (void)e12;
}

Depends on

• Rollback DSU (ds/dsu/rollback_dsu.hpp)

Required by

• Dynamic Connectivity (ds/dynamic_connectivity/all.hpp)

Verified with

• verify/ds/dynamic_connectivity/dynamic_connectivity.test.cpp

Code

#ifndef M1UNE_OFFLINE_DYNAMIC_CONNECTIVITY_HPP
#define M1UNE_OFFLINE_DYNAMIC_CONNECTIVITY_HPP 1

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

#include "../dsu/rollback_dsu.hpp"

namespace m1une {
namespace ds {

struct OfflineDynamicConnectivity {
   private:
    struct Edge {
        int u;
        int v;
        int begin;
        int end;
        bool alive;
    };

    struct Query {
        int u;
        int v;
        int time;
    };

    int _n;
    int _time = 0;
    std::vector<Edge> _edges;
    std::vector<Query> _queries;

    void dfs(
        const std::vector<int>& offset,
        const std::vector<std::pair<int, int>>& stored_edges,
        const std::vector<int>& query_at,
        std::vector<bool>& answer,
        RollbackDsu& dsu,
        int node,
        int base
    ) const {
        int snapshot = dsu.snapshot();
        for (int i = offset[node]; i < offset[node + 1]; i++) {
            auto [u, v] = stored_edges[i];
            dsu.merge(u, v);
        }
        if (node >= base) {
            int query_id = query_at[node - base];
            if (query_id != -1) {
                const Query& query = _queries[query_id];
                answer[query_id] = dsu.same(query.u, query.v);
            }
        } else {
            dfs(offset, stored_edges, query_at, answer, dsu, 2 * node, base);
            dfs(offset, stored_edges, query_at, answer, dsu, 2 * node + 1, base);
        }
        dsu.rollback(snapshot);
    }

   public:
    OfflineDynamicConnectivity() : OfflineDynamicConnectivity(0) {}

    explicit OfflineDynamicConnectivity(int n) : _n(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    int edge_count() const {
        return int(_edges.size());
    }

    int query_count() const {
        return int(_queries.size());
    }

    int operation_count() const {
        return _time;
    }

    void reserve_edges(int count) {
        assert(0 <= count);
        _edges.reserve(count);
    }

    void reserve_queries(int count) {
        assert(0 <= count);
        _queries.reserve(count);
    }

    bool edge_alive(int edge_id) const {
        assert(0 <= edge_id && edge_id < int(_edges.size()));
        return _edges[edge_id].alive;
    }

    int add_edge(int u, int v) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int edge_id = int(_edges.size());
        _edges.push_back(Edge{u, v, _time, -1, true});
        _time++;
        return edge_id;
    }

    bool erase_edge(int edge_id) {
        assert(0 <= edge_id && edge_id < int(_edges.size()));
        Edge& edge = _edges[edge_id];
        if (!edge.alive) return false;
        edge.end = _time;
        edge.alive = false;
        _time++;
        return true;
    }

    int add_query(int u, int v) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int query_id = int(_queries.size());
        _queries.push_back(Query{u, v, _time});
        _time++;
        return query_id;
    }

    std::vector<bool> solve() const {
        std::vector<bool> answer(_queries.size(), false);
        if (_queries.empty()) return answer;
        if (_edges.empty()) {
            for (int query_id = 0; query_id < int(_queries.size()); query_id++) {
                answer[query_id] = _queries[query_id].u == _queries[query_id].v;
            }
            return answer;
        }

        int base = 1;
        while (base < _time) base *= 2;
        int node_count = 2 * base;
        std::vector<int> count(node_count, 0);
        for (const Edge& edge : _edges) {
            int end = edge.alive ? _time : edge.end;
            if (edge.begin < end && edge.u != edge.v) {
                int left = edge.begin + base;
                int right = end + base;
                while (left < right) {
                    if (left & 1) count[left++]++;
                    if (right & 1) count[--right]++;
                    left /= 2;
                    right /= 2;
                }
            }
        }
        std::vector<int> offset(node_count + 1, 0);
        for (int node = 1; node < node_count; node++) offset[node + 1] = offset[node] + count[node];
        std::vector<int> cursor = offset;
        std::vector<std::pair<int, int>> stored_edges(offset[node_count]);
        for (const Edge& edge : _edges) {
            int end = edge.alive ? _time : edge.end;
            if (edge.begin >= end || edge.u == edge.v) continue;
            int left = edge.begin + base;
            int right = end + base;
            while (left < right) {
                if (left & 1) stored_edges[cursor[left]++] = {edge.u, edge.v}, left++;
                if (right & 1) --right, stored_edges[cursor[right]++] = {edge.u, edge.v};
                left /= 2;
                right /= 2;
            }
        }
        std::vector<int> query_at(base, -1);
        for (int query_id = 0; query_id < int(_queries.size()); query_id++) {
            query_at[_queries[query_id].time] = query_id;
        }
        RollbackDsu dsu(_n);
        dsu.reserve_history(int(std::min<std::size_t>(_n, stored_edges.size())));
        dfs(offset, stored_edges, query_at, answer, dsu, 1, base);
        return answer;
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_OFFLINE_DYNAMIC_CONNECTIVITY_HPP

#line 1 "ds/dynamic_connectivity/offline_dynamic_connectivity.hpp"



#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

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



#line 7 "ds/dsu/rollback_dsu.hpp"

namespace m1une {
namespace ds {

struct RollbackDsu {
   private:
    struct HistoryEntry {
        int first;
        int first_value;
        int second;
        int second_value;
    };

    int _n;
    int _component_count;
    std::vector<int> parent_or_size;
    std::vector<HistoryEntry> history;

    static int check_size(int n) {
        assert(0 <= n);
        return n;
    }

   public:
    RollbackDsu() : RollbackDsu(0) {}

    explicit RollbackDsu(int n)
        : _n(check_size(n)), _component_count(_n), parent_or_size(_n, -1) {}

    int size() const {
        return _n;
    }

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

    int component_count() const {
        return _component_count;
    }

    int history_size() const {
        return int(history.size());
    }

    void reserve_history(int count) {
        assert(0 <= count);
        history.reserve(count);
    }

    int leader(int vertex) const {
        assert(0 <= vertex && vertex < _n);
        while (parent_or_size[vertex] >= 0) vertex = parent_or_size[vertex];
        return vertex;
    }

    bool same(int first, int second) const {
        return leader(first) == leader(second);
    }

    int group_size(int vertex) const {
        return -parent_or_size[leader(vertex)];
    }

    int size(int vertex) const {
        return group_size(vertex);
    }

    bool merge(int first, int second) {
        first = leader(first);
        second = leader(second);
        if (first == second) {
            history.push_back(HistoryEntry{-1, 0, -1, 0});
            return false;
        }
        if (-parent_or_size[first] < -parent_or_size[second]) {
            std::swap(first, second);
        }
        history.push_back(HistoryEntry{
            first, parent_or_size[first], second, parent_or_size[second]
        });
        parent_or_size[first] += parent_or_size[second];
        parent_or_size[second] = first;
        _component_count--;
        return true;
    }

    bool undo() {
        if (history.empty()) return false;
        const HistoryEntry entry = history.back();
        history.pop_back();
        if (entry.first == -1) return true;
        parent_or_size[entry.first] = entry.first_value;
        parent_or_size[entry.second] = entry.second_value;
        _component_count++;
        return true;
    }

    int snapshot() const {
        return history_size();
    }

    void rollback(int state) {
        assert(0 <= state && state <= history_size());
        while (history_size() > state) undo();
    }

    std::vector<std::vector<int>> groups() const {
        std::vector<int> leader_buffer(_n);
        std::vector<int> group_sizes(_n, 0);
        for (int vertex = 0; vertex < _n; vertex++) {
            leader_buffer[vertex] = leader(vertex);
            group_sizes[leader_buffer[vertex]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int vertex = 0; vertex < _n; vertex++) {
            result[vertex].reserve(group_sizes[vertex]);
        }
        for (int vertex = 0; vertex < _n; vertex++) {
            result[leader_buffer[vertex]].push_back(vertex);
        }
        result.erase(
            std::remove_if(
                result.begin(), result.end(),
                [](const std::vector<int>& group) { return group.empty(); }
            ),
            result.end()
        );
        return result;
    }
};

}  // namespace ds
}  // namespace m1une


#line 10 "ds/dynamic_connectivity/offline_dynamic_connectivity.hpp"

namespace m1une {
namespace ds {

struct OfflineDynamicConnectivity {
   private:
    struct Edge {
        int u;
        int v;
        int begin;
        int end;
        bool alive;
    };

    struct Query {
        int u;
        int v;
        int time;
    };

    int _n;
    int _time = 0;
    std::vector<Edge> _edges;
    std::vector<Query> _queries;

    void dfs(
        const std::vector<int>& offset,
        const std::vector<std::pair<int, int>>& stored_edges,
        const std::vector<int>& query_at,
        std::vector<bool>& answer,
        RollbackDsu& dsu,
        int node,
        int base
    ) const {
        int snapshot = dsu.snapshot();
        for (int i = offset[node]; i < offset[node + 1]; i++) {
            auto [u, v] = stored_edges[i];
            dsu.merge(u, v);
        }
        if (node >= base) {
            int query_id = query_at[node - base];
            if (query_id != -1) {
                const Query& query = _queries[query_id];
                answer[query_id] = dsu.same(query.u, query.v);
            }
        } else {
            dfs(offset, stored_edges, query_at, answer, dsu, 2 * node, base);
            dfs(offset, stored_edges, query_at, answer, dsu, 2 * node + 1, base);
        }
        dsu.rollback(snapshot);
    }

   public:
    OfflineDynamicConnectivity() : OfflineDynamicConnectivity(0) {}

    explicit OfflineDynamicConnectivity(int n) : _n(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    int edge_count() const {
        return int(_edges.size());
    }

    int query_count() const {
        return int(_queries.size());
    }

    int operation_count() const {
        return _time;
    }

    void reserve_edges(int count) {
        assert(0 <= count);
        _edges.reserve(count);
    }

    void reserve_queries(int count) {
        assert(0 <= count);
        _queries.reserve(count);
    }

    bool edge_alive(int edge_id) const {
        assert(0 <= edge_id && edge_id < int(_edges.size()));
        return _edges[edge_id].alive;
    }

    int add_edge(int u, int v) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int edge_id = int(_edges.size());
        _edges.push_back(Edge{u, v, _time, -1, true});
        _time++;
        return edge_id;
    }

    bool erase_edge(int edge_id) {
        assert(0 <= edge_id && edge_id < int(_edges.size()));
        Edge& edge = _edges[edge_id];
        if (!edge.alive) return false;
        edge.end = _time;
        edge.alive = false;
        _time++;
        return true;
    }

    int add_query(int u, int v) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int query_id = int(_queries.size());
        _queries.push_back(Query{u, v, _time});
        _time++;
        return query_id;
    }

    std::vector<bool> solve() const {
        std::vector<bool> answer(_queries.size(), false);
        if (_queries.empty()) return answer;
        if (_edges.empty()) {
            for (int query_id = 0; query_id < int(_queries.size()); query_id++) {
                answer[query_id] = _queries[query_id].u == _queries[query_id].v;
            }
            return answer;
        }

        int base = 1;
        while (base < _time) base *= 2;
        int node_count = 2 * base;
        std::vector<int> count(node_count, 0);
        for (const Edge& edge : _edges) {
            int end = edge.alive ? _time : edge.end;
            if (edge.begin < end && edge.u != edge.v) {
                int left = edge.begin + base;
                int right = end + base;
                while (left < right) {
                    if (left & 1) count[left++]++;
                    if (right & 1) count[--right]++;
                    left /= 2;
                    right /= 2;
                }
            }
        }
        std::vector<int> offset(node_count + 1, 0);
        for (int node = 1; node < node_count; node++) offset[node + 1] = offset[node] + count[node];
        std::vector<int> cursor = offset;
        std::vector<std::pair<int, int>> stored_edges(offset[node_count]);
        for (const Edge& edge : _edges) {
            int end = edge.alive ? _time : edge.end;
            if (edge.begin >= end || edge.u == edge.v) continue;
            int left = edge.begin + base;
            int right = end + base;
            while (left < right) {
                if (left & 1) stored_edges[cursor[left]++] = {edge.u, edge.v}, left++;
                if (right & 1) --right, stored_edges[cursor[right]++] = {edge.u, edge.v};
                left /= 2;
                right /= 2;
            }
        }
        std::vector<int> query_at(base, -1);
        for (int query_id = 0; query_id < int(_queries.size()); query_id++) {
            query_at[_queries[query_id].time] = query_id;
        }
        RollbackDsu dsu(_n);
        dsu.reserve_history(int(std::min<std::size_t>(_n, stored_edges.size())));
        dfs(offset, stored_edges, query_at, answer, dsu, 1, base);
        return answer;
    }
};

}  // namespace ds
}  // namespace m1une

Back to top page