并查集的拓展 —— 学习笔记
(置顶内容）：这篇内容主要是 种类并查集 和 并查集的按秩合并（启发式合并），且多为基础内容，不需要的dalao就不要浪费时间了，顺便接受我一个orz
（改了一些表意上的错误Ò ~ Ó）
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。不保证理解正确，谨慎参考
我第一次接触到的并查集，作用是 单纯地 查询 元素与各集合 之间的关系，
用处不广，加上今天考试被虐，就有了今天这一篇随笔
（知识点均来自于网友）
（这篇文章就是对从这些链接处的文章中学到的知识做个整理）
不多说，贴链接：
https://blog.csdn.net/C20180602_csq/article/details/57074632
http://www.cnblogs.com/xzxl/p/7341536.html
http://www.cnblogs.com/nanjoqin/p/9069133.html
https://blog.csdn.net/ivy_uu/article/details/66476293
启发式合并
并查集的启发式合并 不会像 带路径压缩的并查集 那样 损失大量信息，也不会像 普通并查集 那样 那么容易被卡
以代码代替语言吧（可能有错误）（然而其实没有）
1 /* 2 普通并查集题目 3 4 输入格式： 5 第一行两个个整数n，m 6 接下来 m 行 ， 7 每行 2个整数 ai，bi 8 表示 节点 ai 与 节点 bi 之间有一条边 9 接下来一行为一个整数 q 10 接下来q行，每行 两个整数 ai，bi 11 表示询问 ai与bi是否存在于同一个集合中 12 13 对于每一个询问，都输出一行， 14 如果ai和bi在同一个集合中， 15 则此行只有一个字符'Y'; 16 反之，这个字符是'N'. 17 18 */ 19 #include<cstdio> 20 #include<iostream> 21 using namespace std; 22 int height[1010],father[1010],n,m; 23 //father——爸爸（常规操作），height——以此节点为根节点的树的高度 24 //n——节点数，m——边数 25 26 int find(int x) { 27 while(father[x] != x) x = father[x]; 28 return x; 29 } 30 31 void qfshb(int x,int y) { 32 int a = find(x); 33 int b = find(y); 34 if(height[a] > height[b]) { 35 father[b] = a; 36 }else if(height[b] > height[a]) { 37 father[a] = b; 38 }else{ 39 father[a] = b; 40 height[b]++; 41 } 42 } 43 int main() { 44 45 scanf("%d%d",&n,&m); 46 for(int i = 1; i <= n; ++i) father[i] = i; 47 for(int i = 1; i <= n; ++i) height[i] = 1; 48 int a,b; 49 for(int i = 1; i <= m; ++i) { 50 scanf("%d%d",&a,&b); 51 qfshb(a,b); 52 } 53 int q; 54 scanf("%d",&q); 55 for(int i = 1; i <= q; ++i) { 56 scanf("%d%d",&a,&b); 57 if(find(a) == find(b)) { 58 puts("Y"); 59 } 60 else { 61 puts("N"); 62 } 63 } 64 return 0; 65 }
这份代码改一下数据输入方法，跑这道题（https://www.luogu.org/problemnew/show/P3367）：
用时: 178ms / 内存: 1052KB
路径压缩的并查集：
用时: 81ms / 内存: 788KB
（慢不了多少吧？）
更
种类并查集
就是开多个并查集，每一个并查集的空间都相同，但表示的意义不相同，
比如 有n个人，维护这n个人之间的两种关系，就要开2*n+1的数组空间，其中，数组标号为（1）至（n）的称为一号并查集，
每个集合中的每个元素都是此集合的“代表"的 “朋友”；
数组标号为（1+n）至（n+n）的称为二号并查集，
每个集合中的每个元素都是此集合的"代表"的“敌人”。
注意，上一段中的粗体字 在 并查集 中 的意义 即为 “根节点”。
这是种类并查集的一种形态，真实状况在实际应用中当然会有所不同
一道纯种类并查集的题：
P2024 [NOI2001]食物链
https://www.luogu.org/problemnew/show/P2024
日常粘题面
题目描述
动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B
吃 C，C 吃 A。
现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道
它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
第一种说法是“1 X Y”，表示 X 和 Y 是同类。
第二种说法是“2 X Y”，表示 X 吃 Y 。
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真
的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
• 当前的话与前面的某些真的话冲突，就是假话
• 当前的话中 X 或 Y 比 N 大，就是假话
• 当前的话表示 X 吃 X，就是假话
你的任务是根据给定的 N 和 K 句话，输出假话的总数。
输入输出格式
输入格式：
从 eat.in 中输入数据
第一行两个整数，N，K，表示有 N 个动物，K 句话。
第二行开始每行一句话（按照题目要求，见样例）
输出格式：
输出到 eat.out 中
一行，一个整数，表示假话的总数。
日常粘样例
输入样例#1：
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
输出样例#1：
3
日常粘数据范围：
说明
1 ≤ N ≤ 5 ∗ 10^4
1 ≤ K ≤ 10^5
-----------------------
（思路借鉴于luogu题解）
这道题如果用种类并查集做，可以维护三个并查集，
ta们的集合元素 对于 本集合代表 的 意义 分别为：
1.域（数组下标范围：1-n） 同类
2.域（数组下标范围：1+n - 2*n） 猎物
3.域（数组下标范围：1+2*n - 3*n） 天敌
这样我们就有了实时的 （1-n号动物所属集合） 之间的 关系信息（当然关系的进程与某人说真话的进程同步），emm……于是……好像……比较……可做qwq。
于是，
对于每一句话，只需要判断这句话是否与 前面的真话构建的关系 冲突，就可以了。
于是可以将 与前面的话矛盾 的 话 的数量统计一下，存储到一个变量里，
最后输出那个变量的值，就好了。
对于每一句话，如果不与前面的话冲突，就按照那句话的描述，更新 并查集 中 的关系，以便 以后的 矛盾判断
（顺便一提，题目已经给出一部分矛盾判断的条件了，真是ti zh wo ye(*1)（拒绝这种拼写方法的诱惑，可能会拯救你的灵魂）（梗乱入）
如果对于 “与前面说过的真话有冲突” 的 判断有疑问，就看代码注释吧；
（网络编辑器又出问题……以后经常保存吧）
对于本题，有一个特殊的地方
看图吧，图中1代表a，2代表b，三代表c
（使用此网站编辑https://csacademy.com/app/graph_editor/）
也就是说，当x 捕食 y 的 关系确认之后，x 的 天敌，是y 的猎物……
代码如下，注释如下
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 5 const int maxn = 50010; 6 int fa[maxn * 3],n,k,x,y,z;//fa意为baba、father，并查集常规操作 7 8 int read() { 9 char c = getchar(); 10 int x = 0, f = 1; 11 while(c < '0' || c > '9') { 12 if(c == '-') f = -f; 13 c = getchar(); 14 } 15 while(c >= '0' && c <= '9') { 16 x = x*10 + c - '0'; 17 c = getchar(); 18 } 19 return x*f; 20 } 21 void print(int x) { 22 if(x < 0) putchar('-'), x = -x; 23 if(x > 9) print(x / 10); 24 putchar(x%10 + '0'); 25 } 26 int find(int x) { 27 if(fa[x] != x) fa[x] = find(fa[x]); 28 return fa[x]; 29 } 30 int uni(int a, int b) { 31 a = find(a); 32 b = find(b); 33 fa[a] = b; 34 } 35 int main() { 36 n = read(); k = read(); 37 for(int i = 1; i <= 3*n; ++i) fa[i] = i;//初始化并查集 38 39 int ans = 0;//ans用来存储“假话的个数 ”这个值 40 while(k--) { 41 z = read(); 42 x = read(); 43 y = read(); 44 /* 45 1.域（数组下标范围：1-n） 同类 46 2.域（数组下标范围：1+n - 2*n） 猎物 47 3.域（数组下标范围：1+2*n - 3*n） 天敌 48 */ 49 if(x > n || y > n) {//正常判断 50 ans++; 51 continue; 52 } 53 switch(z) { 54 case 1://同类语句判断 55 if(find(x+n) == find(y) || find(x+2*n) == find(y)) {//if语句翻译成人话就是if（此前的真话表明x与y之间存在捕食关系） 56 ans++;continue; 57 } 58 uni(x, y); 59 uni(x + n, y + n); 60 uni(x + 2*n, y + 2*n);//实时维护集合之间的关系 61 break; 62 case 2://捕食语句判断 63 if(x == y) { 64 ans++; 65 continue; 66 } 67 if(find(x) == find(y) || find(2*n+x) == find(y)) {//同类之间没有捕食关系，与前面的真语句 确立的 捕食关系 冲突 也不可取 68 ans++; 69 continue; 70 }//x 捕食 y 的关系确立后 71 uni(x,y+2*n);//y的天敌就是x 72 uni(x+n,y);//x的猎物就是y 73 uni(x+2*n,y+n);//x的天敌就是y的猎物 74 break;//以上简写了关系，实际上维护的是集合之间的关系，简写的目的是便于理解 75 } 76 } 77 cout<<ans; 78 return 0; 79 }
我们学校有鸽子耶
注释 *1 :天助我也
