DataStructure/DSU/DSU_rollback.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://judge.yosupo.jp/problem/directedmst

Required by

• DataStructure/DSU/DSU_dynamic_connectivity.h
• Graph/DirectedMST.h

Verified with

• Graph/tests/aizu_grl_2_b_directed_mst.test.cpp
• Graph/tests/directed_mst.test.cpp

Code

// 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 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();
        }
    }
};
// }}}

Back to top page