data_structure/unionfindundo.cpp

Back to top page

• category: data_structure
• View this file on GitHub
  • Last commit date: 2020-03-01 12:39:31+09:00

Verified with

• test/aoj2235.test.cpp

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