并查集例题POJ1988

http://poj.org/problem?id=1998
一开始用的双向的树结构emmmmmm去提交了一下超时了= =因为我没有压缩路径嘛

#include <iostream>
#define N 30004
using namespace std;
int main()
{
    int father[N];
    int son[N];
    for(int i=1;i<N;++i)
    {
        father[i]=i;
        son[i]=i;
    }
    int p;
    cin>>p;
    int flag=0;
    for(int j=1;j<=p;++j)
    {
        char oper;
        int fir,sec;
        cin>>oper;
        if(oper=='M'){
            cin>>fir>>sec;
            int a=fir,b=sec;
            while(son[a]!=a)
            {
                a=son[a];
            }
            while(father[b]!=b)
            {
                b=father[b];
            }
            son[a]=b;
            father[b]=a;
        }
        if(oper=='C'){
            int num=0;
            cin>>fir;
            int a=fir;
            while(son[a]!=a){
                a=son[a];
                ++num;
            }
            if(flag)
                cout<<endl;
            flag=1;
            cout<<num;
        }
    }
    return 0;
}

参考了蓝书
压缩路径的那个find想不明白T_T想了好久
这个root数组名字取的也太有误解性了！！这里存的不是到根节点的距离啊而是到父节点的距离

算法解析.jpg 对递归的理解.jpg

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define N 30004

int n,father[N],root[N],number[N];
//root表示到根结点的距离，number表示这个集合中有多少盒子
void init()
{
    int i;
    for(i=1;i<N;++i){
        father[i]=i;
        root[i]=0;
        number[i]=1;
    }
}

int find(int x)
{
    int fx=father[x];
    if(father[x]!=x){
        fx=find(father[x]);
        root[x]+=root[father[x]];
    }
    return father[x]=fx;
}

void U(int x,int y)
{
    int fx=find(x),fy=find(y);
    father[fy]=fx;
    root[fy]+=number[fx];
    number[fx]+=number[fy];
}

int main()
{
    int i,j;
    init();
    int p;
    cin>>p;
    int flag=0;
    for(int k=1;k<=p;++k)
    {
        char oper;
        cin>>oper;
        if(oper=='C'){
            cin>>i;
            int f=find(i);
            if(flag)
                cout<<endl;
            flag=1;
            cout<<number[f]-root[i]-1;//该集合盒子个数减去再i盒子之上的个数
        }else{
            cin>>i>>j;
            U(i,j);
        }
    }
    return 0;
}