普通并查集（找领导）

并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

  • 合并（Union）：把两个不相交的集合合并为一个集合。
  • 查询（Find）：查询两个元素是否在同一个集合中。

并查集的重要思想在于，用集合中的一个元素代表集合。
并查集初始状态：
v2-09fa3fa35e5411444b327d9cb9a31057_1440w.jpg
通过一系列转化：
v2-3c353bc781c7f3553079d541a9cfdc28_1440w.jpg
最终状态：
v2-6362d8b13705d5ba17b19cdeee453022_1440w.jpg

  1. let fa = [];
  2. let rank = [];
  3. function init(n) {
  4.     for (let i = 1; i <= n; i++) {
  5.         fa[i] = i;
  6.         rank[i] = i;
  7.     }
  8. }
  10. function find(x) {
  11.     return fa[x] === x ? x : (fa[x] = find(fa[x]));
  12. }
  14. function merge(i, j) {
  15.     let x = find(i), y = find(j);
  16.     if (rank[x] <= rank[y]) {
  17.         fa[x] = y;
  18.     } else {
  19.         fa[y] = x;
  20.     }
  21.     if (rank[x] === rank[y] && x != y) {
  22.         rank[y]++;
  23.     }
  24. }
  26. init(6);
  27. merge(2, 3);
  28. merge(1, 3);
  29. merge(3, 4);
  30. merge(5, 6);
  32. let x = 6;
  33. let y = 3;
  34. console.log(find(x) === find(y) ? "Yes" : "No");

这个根据调试得到的所有merge后的fa数组对应元素：
image.png

  • 查询：递归查询该元素的祖元素
  • 合并：把一个集合簇的祖元素接到另一个集合簇的祖元素上
    • rank：判断是x集合接到y上还是y接到x上

      种类并查集（敌人的敌人是朋友）

      开一个两倍大小的并查集。例如，假如我们要维护4个元素的并查集，我们改为开8个单位的。
      我们merge(1, 2+n), merge(1+n, 2);。这里n就等于4，但我写成n这样更清晰。对于1个编号为i的元素，i+n是它的敌人。所以这里的意思就是：1是2的敌人，2是1的敌人。
      v2-9365b0af4ade508a0f1461cfec37f7d2_1440w.jpg
      现在假如我们又知道2和4是敌人，我们merge(2, 4+n), merge(2+n, 4);：
      v2-d86d178ed411c7c0d98402359efe5360_1440w.jpg
      敌人的敌人就是朋友，2和4是敌人，2和1也是敌人，所以这里，1和4通过2+n这个元素间接地连接起来了。这就是种类并查集工作的原理。
      捕食问题：可以用一个三倍大小的并查集进行维护。
      v2-153239130671ad571d49ac366cbf659c_1440w.jpg