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 |
【并查集】 so easy 附代码#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N=30005; int fa[N],son[N],dist[N]; int FA(int x) { if(fa[x]==x) return x; int ans=FA(fa[x]); dist[x]+=dist[fa[x]]; return fa[x]=ans; } void Union(int x,int y) { int fax=FA(x); int fay=FA(y); if(fax==fay) return; fa[fax]=fay; dist[fax]=son[fay]+1; son[fay]+=son[fax]+1; } void init() { for(int i=1;i<N;i++) fa[i]=i; int m;cin>>m; while(m--) { char ss[10]; scanf("%s",ss); if(ss[0]=='M') { int s,t; scanf("%d %d",&s,&t); Union(s,t); // printf("%d : %d %d %d\n",s,FA(s),son[s],dist[s]); // printf("%d : %d %d %d\n",t,FA(t),son[t],dist[t]); } else { int x;scanf("%d",&x); FA(x); printf("%d\n",dist[x]); } } } int main() { // freopen("in.txt","r",stdin); init(); // cout << "Hello world!" << endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator