「NOI2001」食物链

传送门
Luogu

解题思路

带权并查集我不会啊
考虑种类并查集（扩展域并查集的一种）。
开三倍空间，一倍维护本身，二倍维护猎物，三倍维护天敌，然后用并查集搞一搞就好了。

细节注意事项

• 咕咕咕

参考代码

#include<bits/stdc++.h>
using namespace std;
const int maxN=100005;
int n,m,ans,fa[maxN*3];
int find(int u){
    return fa[u]==u?u:fa[u]=find(fa[u]);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n*3;i++)fa[i]=i;
    while(m--){
        int opt,u,v;
        cin>>opt>>u>>v;
        if(u>n||v>n){ans++;continue;}
        if(opt==1)
            if(find(u+n)==find(v)||find(u)==find(v+n))ans++;
            else{
                fa[find(u)]=find(v);
                fa[find(u+n)]=find(v+n);
                fa[find(u+n+n)]=find(v+n+n);
            }
        else
            if(find(u)==find(v)||find(u)==find(v+n))ans++;
            else{
                fa[find(u+n)]=find(v);
                fa[find(u+n+n)]=find(v+n);
                fa[find(u)]=find(v+n+n);
            }
    }
    return cout<<ans,0;
}

完结撒花 \(qwq\)

「NOI2001」食物链

原文：https://www.cnblogs.com/zsbzsb/p/11745902.html