可持久化并查集

可以查询任意版本的并查集，本质就是可持久化数组，将 $f$ 数组与 $siz$ 可持久化

为了减少每次合并操作的修改元素数量，只做按秩合并，不做路径压缩。假设要合并 $a$ 所在元素集合和 $b$ 所在元素集合，集合代表节点和集合大小分别为 $f_a,siz_a,f_b,siz_b(siz_a>siz_b)$，这样每次合并的操作就只有

  1. $f[f_b]=f_a $
  2. $siz[f_a]=siz_a+siz_b$

只需进行两次操作，大大减小了操作量，并且由于启发式合并，每次查询操作也只会跳转 $O(\log n)$ 次。

可撤销并查集

可以按照FIFO回滚所做操作，用一个栈来存储当前版本修改了哪些信息，以便回退到它上一个版本。

由于只维护了两个集合代表节点在合并时的相关信息，同样不能做路径压缩

模板

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
struct DSU {
  std::vector<int> f, siz;
  std::stack<std::pair<int, int>> his;

  DSU() {}
  DSU(int n) { init(n); }

  void init(int n) {
    f.resize(n);
    std::iota(f.begin(), f.end(), 0);
    siz.assign(n, 1);
  }

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

  bool same(int x, int y) { return find(x) == find(y); }

  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({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.top();
      his.pop();
      f[y] = y;
      siz[x] -= siz[y];
    }
  }

  void revert() {
    auto [x, y] = his.top();
    his.pop();
    f[y] = y;
    siz[x] -= siz[y];
  }

  int size(int x) { return siz[find(x)]; }
};

例题

  1. AT_abc302_h

    每个点有两个权值 $A,B$，经过一个点只能选择其中一个，问根节点 0 到其他节点，走最短路径所能取的权值最大种类数量是多少

    对于同一个点上的权值 $A_i,B_i$，用一条边连接，表示可以取这条边两个端点之一

    考虑一张连通图 $G(n,m) $：

    1. 若 $m= n-1$：则 $G$ 为一棵树，按照上述规则可以取到 $n-1$ 个不同权值
    2. 若 $m=n$：可以发现经过调整，可以取到 $n$ 个不同权值
    3. 若 $m>n$：能取到的权值种类数量已到达上限，仍为 $n$ 个

    所以总结规律：假如当前路径加入点 $u$，其两个权值为 $A_u,B_u$，向 $A_u,B_u$ 之间连接一条边，并查集记录连通分量，存储每个连通分量中边的数量：

    1. 如果 $A_u,B_u$ 不在同一连通分量：

      • 若 $A_u,B_u$ 所在连通分量中，存在边数 < 点数的情况，则计数 +1
      • 若 $A_u,B_u$ 所在连通分量中，不存在边数 < 点数的情况，不会产生贡献

    2. 如果 $A_u,B_u$ 在同一连通分量：

      • 若该连通分量，边数 < 点数，则计数+1
      • 否则，不会产生贡献

    利用 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
    int main() {
      std::ios::sync_with_stdio(false);
      std::cin.tie(nullptr);

      int n;
      cin >> n;
      std::vector<pii> ball(n);

      for (int i = 0; i < n; i++) {
        int A, B;
        cin >> A >> B;
        A--;
        B--;
        ball[i] = {A, B};
      }

      std::vector<std::vector<int>> g(n);
      for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
      }

      std::vector<int> ans(n);
      int cnt = 0;
      DSU dsu(n);

      auto dfs = [&](auto&& self, int u, int f) -> void {
        auto [A, B] = ball[u];
        int fA = dsu.find(A), fB = dsu.find(B);
        bool add = false;
        if (fA == fB) {
          if (dsu.siz[fA] > dsu.ecnt[fA]) {
            add = true;
            cnt++;
          }
          dsu.ecnt[fA]++;
        } else {
          if (dsu.siz[fA] < dsu.siz[fB]) {
            std::swap(fA, fB);
          }

          if (dsu.siz[fA] > dsu.ecnt[fA] || dsu.siz[fB] > dsu.ecnt[fB]) {
            add = true;
            cnt++;
          }
          dsu.ecnt[fA] += dsu.ecnt[fB] + 1;
          dsu.siz[fA] += dsu.siz[fB];
          dsu.f[fB] = fA;
        }
        ans[u] = cnt;
        for (int v : g[u]) {
          if (v == f) continue;
          self(self, v, u);
        }

        if (add) {
          cnt--;
        }

        if (fA != fB) {
          dsu.f[fB] = fB;
          dsu.siz[fA] -= dsu.siz[fB];
          dsu.ecnt[fA] -= dsu.ecnt[fB];
        }

        dsu.ecnt[fA]--;
      };
      dfs(dfs, 0, -1);
      
      for (int i = 1; i < n; i++) {
        cout << ans[i] << " \n"[i == n - 1];
      }
      return 0;
    }

  2. CF891C

    给定 $G(n,m)$，每组询问给出若干条边，判断这若干条边是否都能够存在于 $G$ 的一个最小生成树中。

    考虑离线做法，将所有询问存储起来，用 $[u,v,w,id]$ 表示，以 $w$ 为第一关键字，$id$ 为第二关键字排序，这样就能按照 $w$ 和 $id$ 进行分组。

    考虑一个性质：对于一组权值相同的所有边，按照 $kruscal$ 算法流程，无论选择哪些边加入当前最小生成树中，都不会改变其最后生成的图的连通性（考虑反证）。这样在考虑一到 $[u,v,w,id]$ 时，$kruscal$ 算法考虑所有权值小于 $w$ 的边，再看这条边能否加入到最小生成树当中。由于上述性质存在，不必考虑权值比它小的边加入最小生成树时，不同的选择会导致不同的连通性，从而不会对当前选择产生影响。在权值相同，但不同组的 $[u,v,w,id]$ 中，用可撤销并查集去除上一组的影响。

    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
    int main() {
      std::ios::sync_with_stdio(false);
      std::cin.tie(nullptr);
      int n, m;
      cin >> n >> m;

      std::vector<Edge> e;
      e.reserve(m);
      for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e.emplace_back(u - 1, v - 1, w);
      }

      int q;
      cin >> q;
      std::vector<Q> que;
      que.reserve(q);

      for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        for (int j = 0; j < t; j++) {
          int x;
          cin >> x;
          x--;
          que.emplace_back(e[x].u, e[x].v, e[x].w, i);
        }
      }

      std::sort(que.begin(), que.end());
      std::sort(e.begin(), e.end());

      std::vector<bool> ans(q, true);
      DSU dsu(n);

      for (int l = 0, r = 0, p = 0; l < que.size(); l = r + 1, r = l) {
        while (p < m && e[p].w < que[l].w) {
          dsu.merge(e[p].u, e[p].v);
          p++;
        }

        while (r < que.size() && que[r].w == que[l].w && que[r].id == que[l].id) {
          r++;
        }
        r--;

        int j;
        for (j = l; j <= r; j++) {
          if (!dsu.same(que[j].u, que[j].v)) {
            dsu.merge(que[j].u, que[j].v);
          } else {
            ans[que[j].id] = false;
            break;
          }
        }
        int len = j - l;
        while (len--) {
          dsu.revert();
        }
      }
      for (int i = 0; i < q; i++) {
        cout << (ans[i] ? "YES\n" : "NO\n");
      }
      return 0;
    }

  3. CF1444C

    $n$ 个点有 $m$ 个不相容关系，另外有若干组，将任意两组配对，问有多少种配对，可以将两个组中的所有点导出一个二分图（分成两部分，每部分里的所有点之间无不相容关系）。

    使用扩展域并查集来判断相容关系，如果同一组中点无法导出二分图，则事先排除这个组，反之需要加入配对。

    先用 $\binom{k}{2}$ 计算总的配对数量，再从不在同一组的不相容关系中排除不合法的配对数量，使用可撤销并查集撤销上一次不相容关系的影响。

    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
    int main() {
      std::ios::sync_with_stdio(false);
      std::cin.tie(nullptr);
      int n, m, k;
      cin >> n >> m >> k;

      std::vector<bool> check(k, true);
      std::vector<int> belong(n);
      for (int i = 0; i < n; i++) {
        int id;
        cin >> id;
        id--;
        belong[i] = id;
      }

      std::vector<std::array<int, 4>> e;
      e.reserve(m);
      int cnt = k;

      DSU dsu(n * 2);

      for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        if (belong[u] == belong[v]) {
          if (!check[belong[u]]) continue;
          if (dsu.same(u, v)) {
            check[belong[u]] = false;
            cnt--;
          } else {
            dsu.merge(u, v + n);
            dsu.merge(v, u + n);
          }
        } else {
          if (belong[u] > belong[v]) {
            std::swap(u, v);
          }
          e.push_back({belong[u], belong[v], u, v});
        }
      }

      i64 ans = 1LL * (cnt - 1) * cnt / 2;
      
      if (e.empty()) {
        cout << ans << "\n";
        return 0;
      }
      
      std::sort(e.begin(), e.end());
        
      for (int l = 0, r = 0; l < e.size(); l = r + 1, r++) {
        while (r < e.size() && e[l][0] == e[r][0] && e[l][1] == e[r][1]) {
          r++;
        }
        r--;
        if (!check[e[l][0]] || !check[e[l][1]]) continue;
        int t = 0;
        for (int i = l; i <= r; i++) {
          if (dsu.same(e[i][2], e[i][3])) {
            ans--;
            break;
          } else {
            t += dsu.merge(e[i][2], e[i][3] + n);
            t += dsu.merge(e[i][2] + n, e[i][3]);
          }
        }
        while (t--) {
          dsu.revert();
        }
      }
      cout << ans << "\n";
      return 0;
    }