并查集
1.目的
一、合并两个集合
即将其中的一个集合作为另外一个集合的son。
二、判断两个元素是否在同一个集合里面
集合的表示方式是用树来表示(不一定是二叉树)， 每个节点存储的是当前的节点的父亲节点，根节点存储的是该集合的编号。即只需要两个元素(树的节点)一直溯源，查找到根节点对应的编号。若编号相同，则在同一个集合里面。
2.优化
优化的环节主要在于查找根节点的步骤。
朴素的做法是，假设p[x]是x节点的上一个节点.
while(p[x] == x) x = p[x] ;
这样会导致时间复杂度较高。
优化方式：路径压缩。即从一个节点查找根节点之后，将途中的所有的节点的p[x]都指向根节点。这样一旦在需要重复寻根的时候，可以大大节省时间。
3.模板题
一、合并集合
一共有 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≤105
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No
Yes
#include
using namespace std ;
const int N = 100010 ;
int p[N] ;
int find(int num){ //这一步是比较妙的，既找到了num的祖宗节点，而且还实现了路径压缩，每一个节点的父节点都是根节点了
if(p[num] != num)
{
p[num] = find(p[num]) ;
}
return p[num] ;
}
int main(){
int n ,m ;
cin>>n>>m ;
for(int i = 1 ;i <= n ;++i)
p[i] = i ; //相当于初始化，将每一个元素存放到对应的集合中
for(int i = 0 ; i < m ;++i){
char op ;
cin>> op ;
int a , b ;
cin>> a >> b ;
if(op == 'M')
{
p[find(a)] = find(b) ;
}
else
{
if(find(a) == find(b))
cout<<"Yes"< 二、连通块中点的数量
给定一个包含 n个点（编号为 1∼n1∼n）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：
C a b，在点 a 和点b 之间连一条边，aa 和 bb 可能相等；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≤105
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes
2
3
#include
using namespace std ;
const int N = 100010 ;
int n , m ;
int father[N] ;
int find(int num)
{
if(father[num] != num)
father[num] = find(father[num]) ;
return father[num] ;
}
int main()
{
cin>>n>>m ;
int size[N] ;
for(int i = 1 ; i <= n ;++i )
{
father[i] = i ;
size[i] = 1 ;
}
string op;
int a, b ;
for(int i = 0 ; i < m ; ++i )
{
cin>>op ;
if(op == "C")
{
cin>>a>>b ;
int x = find(a) ; int y = find(b) ;
if(x != y)
{
father[x] = y ;
size[y] += size[x] ;
}
}
else if(op == "Q1")
{
cin>>a>>b ;
(find(a) == find(b)) ? puts("Yes") : puts("No") ;
}
else if(op == "Q2")
{
cin>>a ;
cout< 三、食物链
动物王国中有三类动物 A,B,CA,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 句话，输出假话的总数。
输入格式
第一行是两个整数 NN 和 KK，以一个空格分隔。
以下 KK 行每行是三个正整数 D，X，YD，X，Y，两数之间用一个空格隔开，其中 DD 表示说法的种类。
若 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
#include
using namespace std ;
const int N = 100010 ;
int n , m ;
int p[N] ; int dis[N] ;
int find(int num)
{
if(p[num] != num)
{
int t = find(p[num]) ;
dis[num] += dis[p[num]] ;
p[num] = t;
}
return p[num] ;
}
int main()
{
cin >> n >> m ;
int res = 0 ;
for(int i = 1 ;i <= n ;++i)
p[i] = i ;
while(m--)
{
int op , a ,b ;
cin>> op >>a >>b ;
if(a > n || b> n ) res++ ;
else
{
int pa = find(a) ; int pb = find(b) ;
if(op == 1)
{
if(pa == pb && (dis[a] - dis[b]) %3 )
{
res++ ;
}
else if(pa != pb)
{
p[pa] = pb ;
dis[pa] = dis[b] - dis[a] ;
}
}
else
{
if(pa == pb && (dis[a] - dis[b] -1) %3 )
res++ ;
else if(pa != pb)
{
p[pa] = pb ;
dis[pa] = dis[b]+1-dis[a] ;
}
}
}
}
cout< 
