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;
}
上一篇: 详解maven安装教程以及解决安装不成功的解决办法
下一篇: Git和Maven的子模块简单实践