836. 合并集合
https://www.acwing.com/problem/content/838/
# include<iostream>
using namespace std;
const int N = 100010;
int p[N];
int n,m;
int find(int x){ //查询x的根节点并返回 + 路径压缩
if(p[x] != x) p[x] = find(p[x]); //在递归的路径中只要x不是根节点，就将p[x]设置为父节点的根节点
return p[x];
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) p[i]=i;
while(m--){
char op[2];
int a,b;
scanf("%s%d%d",op,&a,&b);
if(op[0]=='M') p[find(a)] = find(b); //设置a的根节点的父节点 为 b的根节点
else{ //查询是否在同一集合中
if(find(a)==find(b)) puts("Yes");
else puts("No");
}
}
}
837. 连通块中点的数量
https://www.acwing.com/problem/content/839/
此题中的n个点在添加了边后，会形成多个连通图，每个连通图可以看做一个集合。查询两个点是否在一个连通块中等价于查询两个数是否在同一集合。所以可以使用并查集来解决，并查集的功能：1、将两个集合以近似O(1)的复杂度进行合并 2、询问两个元素是否在一个集合中。
具体如下：
- 把根节点作为集合的标号，在a、b之间添加一条边就等价于将两个集合合并，等价于将a所在树的根的节点即
find(a)设为 b所在树的根即find(b)，使a所在树 变成 b所在树的子树。同时为了求取第三个问题，要设置一个数组capacity记录每个连通图的点数 即 每个集合的元素数（通过各个树的根确定集合），在合并时如果两个点属于不同的集合则合并后的capacity[rootB]为capacity[rootB]+capacity[rootA]。 - 查询两个点是否在同一连通块中，等价于查询两个数的集合编号是否相等（是否属于同一个根）
- 询问a所在连通块的数量，等价于求
capacity[find(a)]，
# include <iostream>
using namespace std;
const int N = 100010;
int p[N],capacity[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;
capacity[i] = 1; //初始每个点都是一个单独的连通图，集合大小为1
}
while(m--){
int a, b;
char op[5];
scanf("%s", op); //输入操作
if(op[0] == 'C') { //合并
scanf("%d%d", &a, &b);
if(find(a) != find(b)) //只有两个数不属于同一连通块时才更新连通块内点数
capacity[find(b)] += capacity[find(a)];
p[find(a)] = find(b);
}else if(op[1] == '1') { // 查询ab是否在同一集合
scanf("%d%d",&a,&b);
if(find(a) == find(b)) puts("Yes");
else puts("No");
}else { // 查询a所在的连通块中的点数
scanf("%d",&a);
printf("%d\n",capacity[find(a)]);
}
}
return 0;
}
240. 食物链
https://www.acwing.com/problem/content/242/
# include <iostream>
using namespace std;
const int N = 50010;
int p[N],d[N];
int n,k,res;
int find(int x){
if(p[x] != x) {
int tmp = find(p[x]); //记录根
d[x] += d[p[x]]; //在回溯的时候d会更新
p[x] = tmp; //父节点都更新为根节点
}
return p[x];
}
int main(){
cin>>n>>k;
for(int i = 1; i <= n; i++){
p[i] = i; //初始每个点自为一个集合，到父节点的距离为0，而d默认都赋为了0
}
while(k--){
int t,x,y;
cin>>t>>x>>y;
if(x > n || y > n) res++;
else if(t==1){ //同类
int rootX = find(x), rootY = find(y);
if(rootX == rootY && (d[x] - d[y]) % 3 != 0) res ++;
else if(rootX != rootY) { //不在一个集合，但又是同类，所以将其合并
p[rootX] = rootY; //将x树作为子树插入y树
d[rootX] = d[y] - d[x]; //更新rootX到根的距离
}
}else { //x吃y
int rootX = find(x), rootY = find(y);
if(rootX == rootY && (d[x] - d[y] - 1) % 3 != 0) res ++; //x取余后 不在 y取余后的下一位，则错误
else if(rootX != rootY) { //不在一个集合，但存在吃的关系，所以将其合并
p[rootX] = rootY; //将x树作为子树插入y树
d[rootX] = d[y] + 1 - d[x] ; //更新rootX到根的距离
}
}
}
cout<<res<<endl;
}
