#include<iostream>
#include<algorithm>
using namespace std;
class union_find
{
public:
union_find(int n=30000);
~union_find();
int Find(int x);
int Union(int i,int j);
int Move(int i,int j);
int Count(int x);
int XFind(int x);
private:
int *parent;
bool *root;
int *cnt;
int *son;
int *father;
bool *ROOT;
};
int union_find::Count(int x)
{
return cnt[x];
}
union_find::~union_find ()
{
delete []parent;
delete []root;
delete []son;
delete []cnt;
delete []father;
delete []ROOT;
}
union_find::union_find (int n)
{
parent =new int[n+1];
root=new bool [n+1];
son=new int[n+1];
cnt=new int[n+1];
father=new int[n+1];
ROOT=new bool[n+1];
// memset(son,0,sizeof(int)*n);
for(int i=0;i<=n;i++){
cnt[i]=0;
parent[i]=1;
father[i]=son[i]=i;
root[i]=true;
ROOT[i]=true;
}
}
int union_find::XFind(int x)
{
int f=x;
while(!ROOT[f]){f=parent[f];}
while(!ROOT[x]){
int t=parent[x];
parent[x]=f;
x=t;
}
return f;
}
int union_find::Union(int i, int j)
{
i=XFind(i);
j=XFind(j);
if(i==j)return -1;
parent[i]+=parent[j];
ROOT[j]=false;
parent[j]=i;
return i;
}
int union_find::Find(int x)
{
int f=x;
while(!root[f]){f=father[f];}
/**//*printf("%d --",f);
while(!root[x]){
int t=parent[x];
parent[x]=f;
x=t;
}
*/
return f;
}
int union_find::Move(int i, int j)
{
j=XFind(j);
int t=son[i];
//printf("%d %d son::%d\n",i,j,t);
while(!root[t]){
cnt[t]+=cnt[j]+1;
son[t]=son[j];
t=father[t];
}
// root
root[j]=false;
father[j]=son[i];
//father
cnt[t]+=cnt[j]+1;
son[t]=son[j];
return i;
}
int main()
{
int N;
while(scanf("%d",&N)!=EOF){
union_find U(30010);
char op[2];
int x,y;
for(int i=0;i<N;i++){
scanf("%s",op);
if(op[0]=='D'){
scanf("%d %d",&x,&y);
if( U.XFind (x)==U.XFind (y) )continue;
//printf("*****\n");
U.Move (x,y);
U.Union (x,y);
}
else {
scanf("%d",&x);
printf("%d\n",U.Count(x));
}
}
}
return 0;
}
posted on 2009-07-21 21:23
iyixiang 阅读(197)
评论(0) 编辑 收藏 引用 所属分类:
acm