AcWing：并查集
并查集理论基础
并查集的作用是什么：
将两个集合合并。
询问两个元素是否在一个集合当中。
如果不使用并查集，要完成上述两个操作，我们需要：
创建一个数组来表示某个元素在某个集合之中，如belong[x] = a，即x元素在a集合之中。
那么完成第二个操作“询问两个元素是否在同一个集合”的时间复杂度为O(1)，我们只需：
判断if(belong[x] == belong[y])
但是将两个集合合并的效率取决于两个集合中较短的集合的长度，时间复杂度较大O(len)：
len = min(a.size(), b.size()); 再改变belong数组的值。
并查集的作用是，使用近乎O(1)的时间复杂度完成上述两个操作。
并查集基本原理：
每一个集合用一棵树来表示，树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点。
如何判断一个节点是不是树根呢？等价于if(p[x] == x)
如何求x的集合编号？while(p[x] != x) x = p[x];
如何合并两个集合？只需在两个集合中的任意一个加一条边即可，即：假设px是x的集合编号，py是y的集合编号，令p[x] = y即可。
这么看求x的集合编号那一步的时间复杂度还是挺高的，如何优化呢？
从x向上一旦找到根节点后，就将寻找路径上的每一个节点都直接指向根节点，这样这条路径上的所有节点在这之后的“求集合编号”的操作的时间复杂度就为O(1)了。于是并查集在经过优化后的时间复杂度就近似于O(1)了（路径压缩）。
AcWing 836. 合并集合
代码实现
定义一个p[N]数组来记录每个节点的父节点是谁。初始时刻每个元素单独成一个集合，其树根就是自己
#include using namespace std;const int N = 100010;
int p[N];
int n, m;// 路径压缩
int find(int x){if(p[x] != x) p[x] = find(p[x]);return p[x];
}int main(){scanf("%d %d", &n, &m);// initialfor(int i = 1; i <= n; i++){p[i] = i;}while(m--){char operate[2];int a, b;scanf("%s %d %d", operate, &a, &b);if(operate[0] == 'M'){p[find(a)] = find(b);}else{if(find(a) == find(b)) puts("Yes");else puts("No");}}return 0;
}
AcWing 837. 连通块中点的数量
在连通块中连边的操作，就相当于将连通块合并。
#include using namespace std;const int N = 100010;
int p[N], cnt[N];
int n, m;int find(int x){if(p[x] != x) p[x] = find(p[x]);return p[x];
}int main(){scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++){p[i] = i;cnt[i] = 1;}while(m--){string operate;int a, b;cin >> operate;if(operate == "C"){cin >> a >> b;a = find(a), b = find(b);if(a == b) continue;cnt[b] += cnt[a];p[a] = b;}else if(operate == "Q1"){cin >> a >> b;if(find(a) == find(b)) puts("Yes");else puts("No");}else{cin >> a;cout << cnt[find(a)] << endl;}}return 0;
} 注意我开始定义了全局变量count[N]来记录连通块中点的数量，报错：
a.cpp:18:9: error: reference to 'count' is ambiguous18 | count[i] = 1;| ^~~~~因为c++的库函数有关键字count，所以会冲突了，模糊不清。改成int cnt[N]后问题解决。
还有一个细节需要注意：
在C操作时，先把a，b的根结点取出来了：a = find(a), b = find(b);，因此接下来是先将集合a接到集合b下再把a的连通块大小加到b上，还是先把a的连通块大小加到b上再操作集合都是可以的，如果大家没有提前一步的处理，就必须要先加连通块大小再操作集合，否则操作完集合后，a和b的根结点将会重叠，导致输出错误。如下：
// accepted
if(operate == "C"){cin >> a >> b;if(find(a) == find(b)) continue;cnt[find(b)] += cnt[find(a)];p[find(a)] = find(b);
}// wrong
if(operate == "C"){cin >> a >> b;if(find(a) == find(b)) continue;p[find(a)] = find(b);cnt[find(b)] += cnt[find(a)];
}AcWing 240. 食物链
并查集可以用来维护很多额外信息，如上一题，维护了每一个连接块的大小。
本题并查集维护一个距离数组d[N]来描述某节点到其父节点的距离，而距离用来表示食物链中的关系。
由于一共只有三类动物A，B，C，其中A吃B，B吃C，C吃A。这里假设根节点是某一种动物a1，离它距离为1的节点代表一种吃a1的动物a2，离根节点距离为2的节点代表一种吃a2的动物a3，离根节点距离为3的节点代表一种吃a3的动物a4（注意这里a4和a1是同一种动物）。
所以对于d[N]中维护的值来说，任意两个模3同余的值所代表的节点都表示同一种动物。
#include using namespace std;const int N = 50010;
int p[N], d[N];
int n, k;int find(int x){if(p[x] != x){// 存一下find(p[x])的值，因为如果这里直接p[x] = find(p[x])的话，// p[x]就变成根节点了，下面更新d[x]的语句就失效了int t = find(p[x]);d[x] += d[p[x]];p[x] = t;}return p[x];
}int main(){scanf("%d %d", &n, &k);for(int i = 1; i <= n; i++){p[i] = i;}int res = 0;while(k--){int t, x, y;scanf("%d %d %d", &t, &x, &y);// 当前的话中x或y比n大，为假if(x > n || y > n) res++;else{int px = find(x), py = find(y);if(t == 1){// x和y是同类且与前面的话冲突时，为假if(px == py && (d[x] - d[y]) % 3 != 0) res++;else if(px != py){p[px] = py;d[px] = d[y] - d[x];}}else{// x吃y且与前面的话冲突时，为假if(px == py && (d[x] - d[y] - 1) % 3 != 0) res++;else if(px != py){p[px] = py;d[px] = d[y] + 1 - d[x];}}}}printf("%d", res);return 0;
} 注意这里的 d[x] += d[p[x]]里的d[p[x]]是p[x]到它的父节点的距离。原本d[x]存的也是x到父节点的距离，然后p[x]最后变成根节点 ，d[x]才成了x到根节点的距离。
上面可能会带来疑问，为什么我们只在px == py时才进行res的判断？在px != py时只是将两个集合进行合并操作呢？
因为如果x，y动物不属于同一个集合，那么无论说什么，我们都认为这句话是真的：x，y不属于同一集合有两种可能，一种是x，y其中之一或者两者都是新出现的编号，那么新的编号没有和别的编号构成逻辑，直接联系起来即可。第二种是x，y都是之前出现过的编号，并且属于不同的集合, 这两个集合内部的逻辑关系（吃与被吃）与另一个集合没有任何关系，直接联系起来不会影响整体的逻辑关系
一个细节：
x、y经过运算后的d[x]、d[y]可能为负值，因为当 px != py时， d[x] 和 d[y] 的大小关系是不确定的，因此对 d[px] 的处理可能造成结果为负，后续在再次调用 find(x) 时可能会使 d[x] 为负数。所以这里的判断需要特别注意：
(d[x] - d[y]) % 3 != 0
为什么不能写成：
d[x] % 3 != d[y] % 3原因就在上面提到，c++中负数模正数还是负数，就拿 -1 % 3 这个例子来说：
-1 % 3 = (-1) - 3 * (-1 / 3)在数学中和在计算机中虽然他们的计算过程相同，但是计算结果却有些差异。
所以要用第二种写法的话，要写成：
// wrong
d[x] % 3 != d[y] % 3
// right
(d[x] % 3 + 3) % 3 != (d[y] % 3 + 3) % 3AcWing 1249. 亲戚
找亲戚，假设两个人互为亲戚，那么这两个人的亲戚都互为亲戚。本题也是一个并查集的应用，它涉及到了集合的合并，并询问两个点是不是属于同一个集合。
#include using namespace std;const int N = 200010;
int n, m, q;
int p[N];int find(int x){if(p[x] != x) p[x] = find(p[x]);return p[x];
}int main(){scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++){p[i] = i;}while(m--){int a, b;scanf("%d %d", &a, &b);p[find(a)] = find(b);}scanf("%d", &q);while(q--){int c, d;scanf("%d %d", &c, &d);if(find(c) == find(d)) puts("Yes");else puts("No");}return 0;
} 这题不能用cin cout输入输出不然会超时。