可撤销并查集

给定n个结点，q次询问，每次询问分为三类：

1 x y：可以选择将x,y两个点连通，如果已经连通则不操作。

2 ：撤销上一次的操作（若全部撤销完了则不操作）。

3 x y：询问x*,*y是否连通，如果是则输出"YES"，反之输出"NO"，请注意都是大写字母，不包含引号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
struct DSU {
   std::vector<int> siz;
   std::vector<int> f;
   std::vector<std::array<int, 2>> his;

   DSU(int n) : siz(n + 1, 1), f(n + 1) {
       std::iota(f.begin(), f.end(), 0);
   }

   int find(int x) {
       while (f[x] != x) {
           x = f[x];
       }
       return x;
   }

   bool merge(int x, int y) {
       x = find(x);
       y = find(y);
       if (x == y) {
           return false;
       }
       if (siz[x] < siz[y]) {
           std::swap(x, y);
       }
       his.push_back({x, y});
       siz[x] += siz[y];
       f[y] = x;
       return true;
   }

   int time() {
       return his.size();
   }

   void revert(int tm) {
       while (his.size() > tm) {
           auto [x, y] = his.back();
           his.pop_back();
           f[y] = y;
           siz[x] -= siz[y];
       }
   }
};

void solve() {
   int n, m;
   cin >> n >> m;
   DSU dsu(n + 1);
   for (int i = 1; i <= m; i++) {
       int op;
       cin >> op;
       if (op == 1) {
           int x, y;
           cin >> x >> y;
           dsu.merge(x, y);
       } else if (op == 2)
           dsu.revert(dsu.his.size() - 1);
       else {
           int x, y;
           cin >> x >> y;
           if (dsu.find(x) == dsu.find(y))
               cout << "YES" << endl;
           else
               cout << "NO" << endl;
       }
   }
}

可持久化并查集

给定 nn 个集合，第 ii 个集合内初始状态下只有一个数，为 ii。

有 mm 次操作。操作分为 33 种：

  • 1 a b 合并 a,ba,b 所在集合；

  • 2 k 回到第 kk 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态；

  • 3 a b 询问 a,ba,b 是否属于同一集合，如果是则输出 11，否则输出 00。

输入格式

第一行两个整数，n,mn,m。

接下来 mm 行，每行先输入一个数 optopt。若 opt=2opt=2 则再输入一个整数 kk，否则再输入两个整数 a,ba,b，描述一次操作。

输出格式

对每个操作 33，输出一行一个整数表示答案。

Sol:离线用可撤销并查集。操作的撤销有点像dfs的状态回溯，将操作序列的编号作为树的编号，并查集的状态为树的父亲儿子关系。在dfs过程中回答询问，回溯的时候根据需要撤销操作。

实现：注意可能有无效的合并的操作，这时候对应回溯的时候不能撤销。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
struct DSU {
    std::vector<int> siz;
    std::vector<int> f;
    std::vector<std::array<int, 2>> his;

    DSU(int n) : siz(n + 1, 1), f(n + 1) {
        std::iota(f.begin(), f.end(), 0);
    }

    int find(int x) {
        while (f[x] != x) {
            x = f[x];
        }
        return x;
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (siz[x] < siz[y]) {
            std::swap(x, y);
        }
        his.push_back({x, y});
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int time() {
        return his.size();
    }

    void revert(int tm) {
        while ((int)his.size() > tm) {
            auto [x, y] = his.back();
            his.pop_back();
            f[y] = y;
            siz[x] -= siz[y];
        }
    }
    void backlast() {
        assert(his.size());
        // if (his.size() == 0)
        //     return;
        revert(his.size() - 1);
    }
};

void solve() {//可持久化并查集-离线
    int n, m;
    cin >> n >> m;
    vector<vector<int>> e(m + 1);
    DSU dsu(n);
    vector<array<int, 3>> type(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> type[i][0];
        if (type[i][0] == 1 || type[i][0] == 3) {
            e[i - 1].push_back(i);
            cin >> type[i][1] >> type[i][2];
        } else {
            int k;
            cin >> k;
            assert(k < i);
            e[k].push_back(i);
        }
    }
    vector<int> ans(m + 1);
    function<void(int)> dfs = [&](int u) {
        int tmp = dsu.time();

        for (auto v : e[u]) {
            // int tmp = dsu.time();
            auto [op, x, y] = type[v];
            bool flag = 0;
            if (op == 1)
                flag = dsu.merge(x, y);//必须合并成功才能在下面撤销
            else if (op == 3)
                ans[v] = (dsu.find(x) == dsu.find(y)) ? 1 : 0;
            dfs(v);
            // dsu.revert(tmp);
            if (op == 1 && flag)
                dsu.backlast();
        }
    };
    dfs(0);
    for (int i = 1; i <= m; i++) {
        if (type[i][0] == 3) {
            deb(i);
            cout << ans[i] << endl;
        }
    }
}