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