program_contest_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ferin-15/program_contest_library

:heavy_check_mark: data_structure/unionfindundo.cpp

Back to top page

Verified with

Code

// BEGIN CUT
struct UnionFindUndo {
    vector<int> data;
    stack<PII> st;

    UnionFindUndo(int sz) : data(sz, -1) {}

    int find(int k) {
        if(data[k] < 0) return (k);
        return (find(data[k]));
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        st.emplace(x, data[x]);
        st.emplace(y, data[y]);
        if(x == y) return;
        if(data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
    }
    void undo() {
        data[st.top().first] = st.top().second;
        st.pop();
        data[st.top().first] = st.top().second;
        st.pop();
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int k) { return (-data[find(k)]); }
};
// END CUT

#line 1 "data_structure/unionfindundo.cpp"
// BEGIN CUT
struct UnionFindUndo {
    vector<int> data;
    stack<PII> st;

    UnionFindUndo(int sz) : data(sz, -1) {}

    int find(int k) {
        if(data[k] < 0) return (k);
        return (find(data[k]));
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        st.emplace(x, data[x]);
        st.emplace(y, data[y]);
        if(x == y) return;
        if(data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
    }
    void undo() {
        data[st.top().first] = st.top().second;
        st.pop();
        data[st.top().first] = st.top().second;
        st.pop();
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int k) { return (-data[find(k)]); }
};
// END CUT

Back to top page