并查集

 

 

 

 

 

 

代码实现如下：

 

const int N=100;
int father[N];
void Init(int n){
    for(int i=1;i<=n;i++)//初始化
        father[i]=i;
}

int Find(int x){//找祖先
    if(x!=father[x])
        father[x]=Find(father[x]);//把当前结点的到其祖宗路径上的所有结点的值改为祖宗的值
    return father[x];//返回祖宗的值
}

int Merge(int a,int b){
    int p=Find(a);//找出对应的值
    int q=Find(b);
    if(p==q)
        return 0;//不需要合并，不必计算成本
    if(p>q)//将小的值赋值给大的
        father[p]=q;
    else
        father[q]=p;
    return 1;//合并计算总成本
}