0x41并查集

程序自动分析
并查集+离散化

#include<bits/stdc++.h>
using namespace std;
int a[2000005];
int fa[200005];
struct node{
    int x,y,e;
}Node[1000005];
int get(int x){
    if(x==fa[x]) return x;
    return fa[x]=get(fa[x]);
}
void merge(int x,int y){
    fa[get(x)]=get(y);
}
int main(){
    int t;
    cin>>t;
    while(t--){
        for(int i=1;i<=200005;i++) fa[i]=i;
        int n;
        cin>>n;
        int num=1;
        for(int i=1;i<=n;i++){
            cin>>Node[i].x>>Node[i].y>>Node[i].e;
            a[num++]=Node[i].x,a[num++]=Node[i].y;
        }
        num--;
        //离散化
        sort(a+1,a+1+num);
        int m=unique(a+1,a+num+1)-(a+1);
        for(int i=1;i<=n;i++){
            Node[i].x=lower_bound(a+1,a+1+m,Node[i].x)-a;
            Node[i].y=lower_bound(a+1,a+1+m,Node[i].y)-a;
        }
        //---
        for(int i=1;i<=n;i++){
            if(Node[i].e==1)
                merge(Node[i].x,Node[i].y);
        }
        bool flag=true;
        for(int i=1;i<=n;i++){
            if(Node[i].e==0){
                int res1=get(Node[i].x);
                int res2=get(Node[i].y);
                if(res1==res2){
                    flag=false;
                    cout<<"NO"<<endl;
                    break;
                }
            }
        }
        if(flag){
            cout<<"YES"<<endl;
        }
    }
    return 0;
}

银河英雄传说
并查集+边带权

#include<bits/stdc++.h>
using namespace std;
int fa[60005];
int d[60005];
int Size[60005];
int get(int x){
    if(x==fa[x]) return x;
    int root = get(fa[x]);
    d[x] += d[fa[x]];
    return fa[x] = root;
}
void merge(int x,int y){
    x=get(x),y=get(y);
    fa[x]=y;
    d[x]=Size[y];
    Size[y]+=Size[x];
}

int main(){
    int t;
    cin>>t;
    for(int i=1;i<=60000;i++) fa[i]=i,Size[i]=1,d[i]=0;
    while(t--){
        char x;
        int a,b;
        cin>>x>>a>>b;
        if(x=='M'){
            merge(a,b);
        }else{
            if(get(a)==get(b)){
                cout<<abs(d[a]-d[b])-1<<endl;
            }else{
                cout<<-1<<endl;
            }
        }
    }
    return 0;
}