【ACwing】二、 数据结构

• • 836. 合并集合
  • 837. 连通块中点的数量
  • 240. 食物链

https://www.acwing.com/problem/content/838/

# include
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");
        }
    }
    
}

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 
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)]; //先更新b树容量再将a纳入b树
            	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("%dn",capacity[find(a)]);
        }
    }
    return 0;
}

https://www.acwing.com/problem/content/242/

# include 
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]]; //在回溯的时候,由于根返回的p[x]=1,所以其子孩子只需要累加父节点到根的距离即可
        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);
            //当前在一个集合中，可以查看d[]，若发现不是同类，则与k的取值矛盾 
            if(rootX == rootY && (d[x] - d[y]) % 3 != 0)  res ++;
            else if(rootX != rootY) { //不在一个集合中，必须合并更新d值之后才能判断是否同类
                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) { //不在一个集合中，必须合并更新d值之后才能判断是否同类
                p[rootX] = rootY; //将x树作为子树插入y树
                d[rootX] = d[y] + 1 - d[x] ; //更新rootX到根的距离
            }
        }
        
    }
    cout<