欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA 11987 Almost Union-Find (虚点+并查集)

程序员文章站 2024-03-03 18:51:04
...
#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int (x)=(y);(x)<(z);x++)
#define mst(x,y) memset(x,y,sizeof(x))
#define ll long long
const int maxn=1e5+10;
const int maxk=1e7+10;
#define pii pair<int,int> 
#define piii pair<int,pii>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
#define debug cout<<"YES"<<endl;
int gcd(int x,int y){return y?gcd(y,x%y):x;}

int n,m,fa[maxn],p,q;
int sz[maxn],sum[maxn];
void init(){
    rep(i,1,n+1){
        fa[i]=i+n;
        fa[i+n]=i+n;
        sz[i+n]=1;
        sum[i+n]=i;
    }
}
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        init();
        rep(i,0,m){
            int opt;scanf("%d",&opt);
            if(opt==1){
                scanf("%d%d",&p,&q);
                p=find(p),q=find(q);
                if(p==q) continue;/////WA点
                fa[p]=q;
                sz[q]+=sz[p];
                sum[q]+=sum[p];
            }else if(opt==2){
                scanf("%d%d",&p,&q);
                int fp=find(p),fq=find(q);
                sz[fp]--,sum[fp]-=p;
                sz[fq]++,sum[fq]+=p;
                fa[p]=fq;
            }else{
                scanf("%d",&p);
                p=find(p);
                printf("%d %d\n",sz[p],sum[p]);
            }
        }
    }
    return 0;
}