| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
ac代码!(模板题)#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int fa[30005],ran[30005],size[30005];
inline void init(){
for(int i=1;i<=30005;i++){
fa[i]=i;
ran[i]=0;
size[i]=1;
}
}
int find(int x){
if(x==fa[x]) return x;
else{
int t=fa[x];
fa[x]=find(fa[x]);
ran[x]+=ran[t];
return fa[x];
}
}
inline void merge(int i,int j){
int x=find(i),y=find(j);
fa[x]=y;
ran[x]+=size[y];
size[y]+=size[x];
}
int main(){
int t,a,b;
char ch;
init();
scanf("%d",&t);
while(t--){
scanf(" %c",&ch);
if(ch=='M'){
scanf("%d%d",&a,&b);
merge(a,b);
}
else{
scanf("%d",&a);
find(a);
printf("%d\n",ran[a]);
}
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator