DataStructure/DSU/DSU_dynamic_connectivity.h

• View this file on GitHub
• Last update: 2023-01-07 01:46:12+08:00
• Link: https://codeforces.com/gym/100551/problem/A
• Link: https://www.spoj.com/problems/DYNACON2/

Depends on

• DataStructure/DSU/DSU_rollback.h

Code

#include "DSU_rollback.h"

// Index from 0
// Tested:
// - https://codeforces.com/gym/100551/problem/A
// - https://www.spoj.com/problems/DYNACON2/
//
// Dynamic connectivity {{{
namespace DynamicConnectivity {
    enum QueryType { ADD, REM, IS_CONNECTED, N_COMPONENTS };
    struct Query {
        QueryType typ;
        int u, v;
    };

    // Segment tree: for each node maintaining [l, r], store all the
    // edges covering all times between l and r.
    vector<vector<pair<int,int>>> edges;
    vector<Query> queries;

    void update(int i, int l, int r, int u, int v, const pair<int,int>& e) {
        if (v < l || r < u) return;
        if (u <= l && r <= v) {
            edges[i].push_back(e);
            return;
        }
        int mid = (l + r) / 2;
        update(i*2, l, mid, u, v, e);
        update(i*2+1, mid+1, r, u, v, e);
    }

    void dfs(
            int i, int l, int r,
            int current_time, int n_connected_components,
            DSU& dsu,
            vector<int>& res) {
        for (auto [u, v] : edges[i]) {
            if (!dsu.same_component(u, v)) {
                --n_connected_components;
            }
            dsu.join(u, v, current_time);
        }

        if (l == r) {
            if (queries[l].typ == IS_CONNECTED) {
                int u = queries[l].u, v = queries[l].v;
                res[l] = dsu.same_component(u, v);
            } else if (queries[l].typ == N_COMPONENTS) {
                res[l] = n_connected_components;
            }
            return;
        }

        int mid = (l + r) / 2;
        dfs(i*2, l, mid, current_time + 1, n_connected_components, dsu, res);
        dsu.rollback(current_time);
        dfs(i*2+1, mid+1, r, current_time + 1, n_connected_components, dsu, res);
    }

    // Returns: vector of length |Q|
    // The i-th element is answer for i-th query
    //     -1 if the i-th query is ADD or REM
    vector<int> solve(int n, const vector<Query>& _queries) {
        queries = _queries;
        edges.clear();
        edges.resize(4 * queries.size());

        map<pair<int,int>, int> addTimes;

        int q = queries.size();
        for (int i = 0; i < q; ++i) {
            const auto& query = queries[i];
            if (query.typ == ADD) {
                int u = query.u, v = query.v;
                if (u > v) swap(u, v);
                auto p = make_pair(u, v);
                assert(!addTimes.count(p));

                addTimes[p] = i;
            } else if (query.typ == REM) {
                int u = query.u, v = query.v;
                if (u > v) swap(u, v);
                auto p = make_pair(u, v);
                assert(addTimes.count(p));

                update(1, 0, q-1, addTimes[p], i, p);

                addTimes.erase(p);
            }
        }
        for (const auto& [e, startTime] : addTimes) {
            update(1, 0, q-1, startTime, q-1, e);
        }

        vector<int> res(queries.size(), -1);
        if (q > 0) {
            DSU dsu(n);
            dfs(1, 0, q-1, 0, n, dsu, res);
        }
        return res;
    }
}
// }}}

#line 1 "DataStructure/DSU/DSU_rollback.h"
// Tested:
// - (dynamic connectivity) https://codeforces.com/gym/100551/problem/A
// - (used for directed MST) https://judge.yosupo.jp/problem/directedmst
//
// 0-based
// DSU with rollback {{{
struct Data {
    int time, u, par;  // before `time`, `par` = par[u]
};

struct DSU {
    vector<int> par;
    vector<Data> change;

    DSU(int n) : par(n + 5, -1) {}

    // find root of x.
    // if par[x] < 0 then x is a root, and its tree has -par[x] nodes
    int getRoot(int x) {
        while (par[x] >= 0)
            x = par[x];
        return x;
    }

    bool same_component(int u, int v) {
        return getRoot(u) == getRoot(v);
    }

    // join components containing x and y.
    // t should be current time. We use it to update `change`.
    bool join(int x, int y, int t) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y) return false;

        //union by rank
        if (par[x] < par[y]) swap(x, y); 
        //now x's tree has less nodes than y's tree
        change.push_back({t, y, par[y]});
        par[y] += par[x];
        change.push_back({t, x, par[x]});
        par[x] = y;
        return true;
    }

    // rollback all changes at time > t.
    void rollback(int t) {
        while (!change.empty() && change.back().time > t) {
            par[change.back().u] = change.back().par;
            change.pop_back();
        }
    }
};
// }}}
#line 2 "DataStructure/DSU/DSU_dynamic_connectivity.h"

// Index from 0
// Tested:
// - https://codeforces.com/gym/100551/problem/A
// - https://www.spoj.com/problems/DYNACON2/
//
// Dynamic connectivity {{{
namespace DynamicConnectivity {
    enum QueryType { ADD, REM, IS_CONNECTED, N_COMPONENTS };
    struct Query {
        QueryType typ;
        int u, v;
    };

    // Segment tree: for each node maintaining [l, r], store all the
    // edges covering all times between l and r.
    vector<vector<pair<int,int>>> edges;
    vector<Query> queries;

    void update(int i, int l, int r, int u, int v, const pair<int,int>& e) {
        if (v < l || r < u) return;
        if (u <= l && r <= v) {
            edges[i].push_back(e);
            return;
        }
        int mid = (l + r) / 2;
        update(i*2, l, mid, u, v, e);
        update(i*2+1, mid+1, r, u, v, e);
    }

    void dfs(
            int i, int l, int r,
            int current_time, int n_connected_components,
            DSU& dsu,
            vector<int>& res) {
        for (auto [u, v] : edges[i]) {
            if (!dsu.same_component(u, v)) {
                --n_connected_components;
            }
            dsu.join(u, v, current_time);
        }

        if (l == r) {
            if (queries[l].typ == IS_CONNECTED) {
                int u = queries[l].u, v = queries[l].v;
                res[l] = dsu.same_component(u, v);
            } else if (queries[l].typ == N_COMPONENTS) {
                res[l] = n_connected_components;
            }
            return;
        }

        int mid = (l + r) / 2;
        dfs(i*2, l, mid, current_time + 1, n_connected_components, dsu, res);
        dsu.rollback(current_time);
        dfs(i*2+1, mid+1, r, current_time + 1, n_connected_components, dsu, res);
    }

    // Returns: vector of length |Q|
    // The i-th element is answer for i-th query
    //     -1 if the i-th query is ADD or REM
    vector<int> solve(int n, const vector<Query>& _queries) {
        queries = _queries;
        edges.clear();
        edges.resize(4 * queries.size());

        map<pair<int,int>, int> addTimes;

        int q = queries.size();
        for (int i = 0; i < q; ++i) {
            const auto& query = queries[i];
            if (query.typ == ADD) {
                int u = query.u, v = query.v;
                if (u > v) swap(u, v);
                auto p = make_pair(u, v);
                assert(!addTimes.count(p));

                addTimes[p] = i;
            } else if (query.typ == REM) {
                int u = query.u, v = query.v;
                if (u > v) swap(u, v);
                auto p = make_pair(u, v);
                assert(addTimes.count(p));

                update(1, 0, q-1, addTimes[p], i, p);

                addTimes.erase(p);
            }
        }
        for (const auto& [e, startTime] : addTimes) {
            update(1, 0, q-1, startTime, q-1, e);
        }

        vector<int> res(queries.size(), -1);
        if (q > 0) {
            DSU dsu(n);
            dfs(1, 0, q-1, 0, n, dsu, res);
        }
        return res;
    }
}
// }}}

Back to top page