[C++知识库]练习16，并查集模板&NOI2001食物链【并查集】

并查集一般模板：

void init(){ //初始化
    for(int i=1;i<=n;i++) fa[i]=i;
}

int find(int x){ //寻找根节点
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}

void unity(int x,int y){ //合并集合，将x集根节点并入y集根节点
    fa[find(x)]=find(y);
}

并查集模板题：P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
int n,m;
int fa[10010];
void init(){
    for(int i=1;i<=n;i++) fa[i]=i;
}
int find(int x){
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
int main(){
    cin >> n >> m;
    init();
    for(int i=1;i<=m;i++){
        int z,x,y;
        cin >>  z >> x >> y;
        if(z==1){
            fa[find(x)]=find(y);
        }
        if(z==2){
            if(find(x)==find(y)) puts("Y");
            else puts("N");
        }
    }
    return 0;
}

P2024 [NOI2001] 食物链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
int n,k;
int fa[150010],ans=0;
void init(){
    for(int i=1;i<=n*3;i++) fa[i]=i; //一倍是本身，二倍是猎物，三倍是天敌
}

int find(int x){
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}

void unity(int x,int y){
    fa[find(x)]=find(y);
}
int main(){
    cin >> n >> k;
    init();
    for(int i=1;i<=k;i++){
        int d,x,y;
        cin >>  d >> x >> y;
        if(x>n || y>n) {ans++; continue;}

        if(d==1){
            if(find(x+n)==find(y) || find(x+n*2)==find(y)) {ans++; continue;}
            unity(x,y);
            unity(x+n,y+n);
            unity(x+n*2,y+n*2);
        }
        if(d==2){
            if(find(x)==find(y)) {ans++; continue;}
            if(find(x)==find(y+n) || find(x)==find(y)) {ans++; continue;}
            unity(x,y+2*n);
            unity(x+n,y);
            unity(x+n*2,y+n);
        }
    }
    cout << ans <<endl;
    return 0;
}