还是并查集的高级应用
思想和食物链一样，就是下面那篇博客的思想：
http://blog.csdn.net/xiaomajiyue/archive/2011/02/16/6188553.aspx
嘻嘻，再次提到了食物链，看来彻底搞懂食物链真的很重要
#include<iostream> using namespace std; #define N 30005 int c[N],p[N],r[N]; void init(int n) { for(int i=1;i<=n;i++) { p[i]=i; r[i]=0; c[i]=1; } } int find(int x) { if(p[x]==x) return x; int temp=p[x]; p[x]=find(p[x]); r[x]+=r[temp]; return p[x]; } void merge(int rx,int ry) { r[rx]=c[ry]; c[ry]+=c[rx]; p[rx]=ry; } int main() { int p,x,y,xx,yy; char chr; init(30000); scanf("%d",&p); getchar(); while(p--) { scanf("%c",&chr); if(chr=='C') { scanf("%d",&x); xx=find(x); printf("%d/n",r[x]); } else { scanf("%d%d",&x,&y); xx=find(x),yy=find(y); merge(xx,yy); } getchar(); } return 0; }
