连通块中点的数量题目链接

837. 连通块中点的数量 - AcWing题库

连通块中点的数量题目类型

并查集

连通块中点的数量代码

#include<iostream>
​
using namespace std;
​
const int N = 100010;
​
int n, m;
int p[N], sz[N];
​
int find(int x) // 返回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;
        sz[i]=1;
    }
    while(m--)
    {
        char op[5];
        int a, b;
        scanf("%s",op);
        
        if(op[0]=='C')
        {
            scanf("%d%d",&a,&b);
            if(find(a)!=find(b)) sz[find(b)]+=sz[find(a)];
            p[find(a)]=find(b);
        }
        else if(op[1]=='1'){
            scanf("%d%d",&a,&b);
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
        }
        else{
            scanf("%d",&a);
            printf("%d\n",sz[find(a)]);
        }
    }
    return 0;
}

食物链题目链接

837. 连通块中点的数量 - AcWing题库

食物链题目类型

并查集

食物链题目思路

余1：可以吃根节点

余2：可以被根节点吃

余0：与根节点是同类

食物链代码

#include<iostream>
​
using namespace std;
​
const int N = 50010;
​
int n, m;
int p[N], d[N];
​
int find(int x) // 返回x的祖宗节点 + 路径压缩
{
    if(p[x] != x)
    {
        int u = p[x]; // u记录旧的父节点
        p[x] = find(p[x]); // 路径压缩
        d[x] += d[u];
    }
    return p[x];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    
    int res = 0;
    while(m--)
    {
        int t, x, y;
        scanf("%d%d%d",&t,&x,&y);
        
        if(x>n|| y>n) res++;
        else
        {
            int px = find(x), py = find(y);
            if(t==1)
            {
                if(px==py && (d[x]-d[y])%3) res++;
                else if(px!=py)
                {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
                if (px==py && (d[x]-d[y]-1)%3) res ++;
                else if(px != py)
                {
                    p[px]=py;
                    d[px]=d[y]+1-d[x];
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}