无限种类并查集——pku1988

并查集的题目也做的差不多了，关键还是理解find（），un（）的过程……

接着搜索一礼拜……

#include<stdio.h>
#define N 30009

int f[N];
int all[N];
int up[N];

int find(int pos)
{
    if(f[pos]==-1)
        return pos;
    int temp;
    temp=f[pos];
    f[pos]=find(f[pos]);
    up[pos]+=up[temp];
    
    return f[pos];
}

void un(int a,int b)
{
    int fa=find(a);
    int fb=find(b);
    
    f[fb]=fa;
    up[fb]=all[fa];
    all[fa]+=all[fb];
}

int main()
{
    int p,a,b;
    
    register int i;//看效果 
    char ss;
    
    scanf("%d",&p);
    {
        for(i=1;i<N;i++)
        {
            f[i]=-1;
            all[i]=1;
            up[i]=0;
        }
        for(i=1;i<=p;i++)
        {
            getchar();
            scanf("%c",&ss);
            if(ss=='M')
            {
                scanf("%d%d",&a,&b);
                un(a,b);
            }
            else
            {
                scanf("%d",&a);
                printf("%d\n",all[find(a)]-up[a]-1);
            }
        }
    }
}