P2024 [NOI2001] 食物链

原题链接

题解

带权并查集的应用，普通的并查集只能表示结点间的一种关系（如同一集合中的都是朋友）。而带权并查集的结点权值表示该结点与根结点的关系。相对应，带权并查集的路径压缩也复杂了一点。

code

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,k;
int father[N],dis[N];
void build(){
    for (int i=1;i<=n;i++){
        father[i]=i;
        dis[i]=0;
    }
}
int find(int x){
    if (father[x]!=x){
        int r=find(father[x]);
        dis[x]=(dis[x]+dis[father[x]])%3;
        father[x]=r;
    }
    return father[x];
}
int main(){
    cin>>n>>k;
    build();
    int sum=0;
    for (int i=1;i<=k;i++){
        int d,x,y;
        cin>>d>>x>>y;
        if (x>n || y>n || (x==y && d==2)){
            sum++;
            continue;
        }
        int fx=find(x),fy=find(y);
        if (fx==fy){
            if ((dis[y]-dis[x]+3)%3!=d-1) sum++;
        }
        else {
            dis[fy]=(dis[x]+d-1-dis[y]+3)%3;
            father[fy]=fx;
        }
    }
    cout<<sum<<endl;
    return 0;
}