一、概念：
1.并查集是什么：
并查集本质就是集合
那它能做什么呢？这就要看前两个字 - “并” 和 “查”。
集合的一些操作，例如，交集，并集等等，这里的 “并” 其实就指的是并集操作，两个集合合并后就会变成一个集合。例如：
{1,3,5,7} U {2,4,6,8} = {1,2,3,4,5,6,7,8}
那 “查” 又是什么呢？集合本身只是容器，最终还是要知道里面存的是什么元素，因此这里的 “查” 是对于集合中存放的元素来说的，即要查找这个元素在不在集合中，还要确定这个元素是在哪个集合中。
2.并查集怎么用：
并查集可以进行集合合并的操作（并）
并查集可以查找元素在哪个集合中（查）
并查集维护的是一堆集合（集）
3.例子：
有8个元素：14, 35, 48, 87, 65, 20。
集：把个位相同的数字归在同一个集合。集合划分为如下：
{14}, {35, 65}, {48}, {87}, {20}
查：给定一个元素，得到这个元素属于哪个集合。例如：
给定元素14，可以得出：14 位于第一个集合。
给定元素65，可以得出：65 位于第二个集合。
给定元素20，可以得出：20 位于第五个集合。
并：将两个集合合并，例如将个位为偶数的集合合并的到第一个集合，个位为奇数的集合合并到第二个集合，结果如下：
{14, 48, 20}, {35, 65, 87}
4.代码模板：
朴素并查集： int p[N]; //存储每个点的祖宗节点 // 返回x的祖宗节点 int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } // 初始化，假定节点编号是1~n for (int i = 1; i <= n; i ++ ) p[i] = i; // 合并a和b所在的两个集合： p[find(a)] = find(b);
(2)维护size的并查集： int p[N], size[N]; //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量 // 返回x的祖宗节点 int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } // 初始化，假定节点编号是1~n for (int i = 1; i <= n; i ++ ) { p[i] = i; size[i] = 1; } // 合并a和b所在的两个集合： size[find(b)] += size[find(a)]; p[find(a)] = find(b);
(3)维护到祖宗节点距离的并查集： int p[N], d[N]; //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离 // 返回x的祖宗节点 int find(int x) { if (p[x] != x) { int u = find(p[x]); d[x] += d[p[x]]; p[x] = u; } return p[x]; } // 初始化，假定节点编号是1~n for (int i = 1; i <= n; i ++ ) { p[i] = i; d[i] = 0; } // 合并a和b所在的两个集合： p[find(a)] = find(b); d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
二、基本原理：
三、例题：
1.合并集合(朴素并查集)
一共有 n个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m 个操作，操作共有两种：
- M a b，将编号为 a 和 b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
- Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；
输入格式
第一行输入整数 n和 m。
接下来 m行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。
输出格式
对于每个询问指令 Q a b，都要输出一个结果，如果 a和 b在同一集合内，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤10^5
输入样例：
4 5 M 1 2 M 3 4 Q 1 2 Q 1 3 Q 3 4
输出样例：
Yes No Yes
思路：
- 初始化：
int n; cin>>n;//(n=8) for(int i = 0; i < n; i ++) p[i] = i;
2.查找 + 路径压缩
int find(int x) { //返回x的祖先节点 + 路径压缩 //祖先节点的父节点是自己本身 if(p[x] != x) { //将x的父亲置为x父亲的祖先节点,实现路径的压缩 p[x] = find(p[x]); } return p[x]; }
3.合并操作
if(op == ‘M’) p[find(a)] = find(b); //将a的祖先点的父节点置为b的祖先节点
4.查找
find(a) == find(b)
#include<iostream> using namespace std; const int N=100010; int p[N];//存放代表元素 //查找 x 所属的集合，就是 x 元素的代表元素 int find(int x) { //如果 x 的代表元素不是他自己，就递归的x的代表元素修改为代表元素的代表元素 if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main() { int n,m; cin>>n>>m; for(int i=0;i<n;i++)p[i]=i; while(m--) { char op; int a,b; cin>>op>>a>>b; //合并a b所在的两个集合 if(op=='M') { int pa = find(a);//找到 a 所在集合的代表元素 int pb = find(b);//找到 b 所在集合的代表元素 if(pa != pb)//如果不是同一个，则属于不同集合，需要合并 { p[pa] = pb;//将a所在集合代表元素的代表元素设置为b所在集合的代表元素。 } } else { int pa = find(a);//找到 a 所在集合的代表元素 int pb = find(b);//找到 b 所在集合的代表元素 //判断 a 和 b 是否有同一个代表元素 if(pa == pb)cout<<"Yes"<<endl; else cout<<"No"<<endl; } } return 0; }
2.连通块中点的数量(维护size的并查集)
给定一个包含 n个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 m个操作，操作共有三种：
- C a b，在点 a 和点 b之间连一条边，a和 b 可能相等；
- Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
- Q2 a，询问点 a 所在连通块中点的数量；
输入格式
第一行输入整数 n和 m。
接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤10^5
输入样例：
5 5 C 1 2 Q 1 1 2 Q 2 1 C 2 5 Q 2 5
输出样例：
Yes 23
1.初始化：
void init() { for (int i=1; i<=n; i++) { fa[i] = i; size[i] = 1; } }
2.找主源：
int find(int x) { if(fa[x]==x) return x; else return fa[x] = find(fa[x]); }
3.合并连通块
void merge(int a,int b) { int x = find(a); int y = find(b); fa[x] = y; size[y] += size[x]; }
4.询问是否连通
bool ask(int a,int b) { return find(a)==find(b); }
#include<iostream> using namespace std; const int N=100010; int p[N],s[N]; void init(int n) { //初始化 for(int i=0;i<n;i++) { p[i]=i; s[i]=1; } } int find(int x) { if(x==p[x])return x; else return p[x]=find(p[x]); } void merge(int a,int b) { int pa=find(a); int pb=find(b); p[pa]=pb; s[pb]+=s[pa]; } bool ask(int a,int b) { return find(a)==find(b); } int main() { int n,m; cin>>n>>m; init(n); while(m--) { int a,b; string op; cin>>op; if(op=="C") { cin>>a>>b; if(!ask(a,b)) merge(a,b); } else if(op=="Q1") { cin>>a>>b; if(ask(a,b))cout<<"Yes"<<endl; else cout<<"No"<<endl; } else { cin>>a; cout<<s[find(a)]<<endl; } } return 0; }
3.食物链（维护到祖宗节点距离的并查集）
动物王国中有三类动物 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句话，输出假话的总数。
输入格式
第一行是两个整数 N和 K，以一个空格分隔。
以下 K行每行是三个正整数 D，X，Y两数之间用一个空格隔开，其中 D 表示说法的种类。
若 D=1，则表示 X 和 Y 是同类。
若 D=2，则表示 X 吃 Y。
输出格式
只有一个整数，表示假话的数目。
数据范围
1≤N≤50000
0≤K≤100000
输入样例：
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
输出样例：
3
思路：
本题的关系有三层 -> a -> b -> c -> ，但不同的是本题的关系是有向的，也就是说a和b如果是敌对关系，那么b和a就不是敌对关系
(带权并查集) 时间复杂度O(1)
任意的X和Y两个动物，总共有三种关系
1. X和Y是同类
2. X吃Y(X是捕食者)
3. X被Y吃(X是猎物)
问题的核心在于对于任意的X和Y，如何去确定X和Y的关系。
题目说有三类动物，形成了一个环形，A吃B，B吃C，C吃A，这就和数学中的取模很相似，0->1->2->3(3即是0)
我们采用数组d[i]来代表i节点到父节点的代数，通过d mod3转化为0,1,2三代的关系
d[x]mod3==d[y]mod3
对应X与Y为同类，具体可以是，同为0代，同为1代，同为2代
(d[x]+1)mod3==d[y]mod3
对应X吃Y，具体可以有三种情况
(d[x]+2)mod3==d[y]mod3
对应X被Y吃，同上
至此我们已经判断出X和Y的关系，也能很容易判断真话假话。
假话：
1. X或Y过界
2. X和Y都已经出现过（在并查集中），并且当前关系与并查集中的关系不同
真话：
1.X和Y未都出现过（需要加入并查集）
- X和Y已经出现过，并且当前关系与并查集中的关系一致
权值传递过程图解：
取余3
1.余1：可以吃根节点 2.余2：可以被根节点吃 3.余0与根节点是同类
0代表同类，1代表x吃y，2代表y吃x
merge操作原理图解
#include<iostream> #include<cstdio> using namespace std; const int N = 1e5+5; int p[N],d[N]; //p[i] 代表i的父节点 //d[i] 代表i到它的父节点距离,在全局变量中默认值为0 int find(int x) { if(x!=p[x]) { int t = find(p[x]); //此行会把p[x]的父节点更新成祖宗节点 d[x] += d[p[x]]; //d[p[x]]就指p[x]到祖宗节点的距离 p[x] = t; } return p[x]; } int main() { int n,k; cin>>n>>k; for(int i=0;i<n;i++) p[i] = i; int cnt = 0;//代表假话个数 while(k--) { int no,x,y; cin>>no>>x>>y; if(x>n || y>n) cnt++; else { int rx=find(x),ry = find(y); if(no==1) { //rx==ry同类并且到根节点距离不等于0为假话 if(rx == ry && (d[x]-d[y])%3!=0) cnt++; //rx!=ry不在一个集合里面 else if(rx!=ry) { //执行合并集合操作 p[rx] = ry; d[rx] = d[y] - d[x]; //此处增加的距离是上面if条件的相反数 } } else { //rx==ry同类并且到根节点距离不等于0为假话 if(rx == ry && (d[x]-d[y]-1)%3!=0) cnt++; //rx!=ry else if(rx!=ry) { //执行合并集合操作 p[rx] = ry; d[rx] = d[y] + 1 - d[x]; //此处增加的距离是上面if条件的相反数 } } } } printf("%d\n",cnt); return 0; }
