食物链之带权并查集解法

直接看题：https://www.acwing.com/problem/content/description/242/

下面就是代码的实现了，因为自己与自己肯定是同类我们初始化为0.

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
int fk,x,y;
int fa[100010],d[100010];
int find(int x)
{
    if(fa[x]!=x)
    {
        int t=fa[x];
        fa[x]=find(fa[x]);
        d[x]+=d[t];

    }
    return fa[x];
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) fa[i]=i;
    int res=0;
    while(k--)
    {
        cin>>fk>>x>>y;
        if(x>n||y>n) res++;
        else if(fk==1)
        {
            int x1=find(x),y1=find(y);
            if(x1==y1&&(d[x]-d[y])%3) res++;
            else if(x1!=y1)
            {
                fa[x1]=y1;
                d[x1]=d[y]-d[x]+3;
            }
        }
        else{
            int x1=find(x),y1=find(y);
            if(x1==y1&&(d[x]-d[y]-1)%3) res++;
            else if(x1!=y1)
            {
                fa[x1]=y1;
                d[x1]=d[y]-d[x]+4;
            }
        }
    }
    cout<<res;
}

原文地址：https://blog.csdn.net/cocoack/article/details/140333354

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！