并查集

一、并查集定义、基本操作、路径压缩

并查集性质:并查集产生的每一个集合都是一棵树

1、并查集定义及初始化

//用一个数组实现并查集
int father[N];
//初始化
for(int i=1;i<=N;i++)
{
    father[i]=i;
}

 

2、查找

规定同一个集合中只存在一个根结点，因此查找操作即对给定的结点寻找其根结点的过程。实现方式可以是递归或递推

①递推，findFather函数返回元素x所在集合的根结点

int findFather(int x)
{
    while(x!=father[x]){
        x=father[x];   //获取自己的父亲结点
    }
    return x;
}

②递归

int findFather(int x)
{
    if(x==father[x]) return x;  //如果找到根结点，则返回根结点编号x
    else return findFather(father[x]); //否则递归判断x的父亲结点是否是根结点
}

 

3、合并

把给定的两个元素所在的集合合并
思路：
①对于给定的两个元素a、b,判断它们是否属于同一个集合，可以调用上面的查找函数，对这两个元素a,b分别查找根结点，然后判断其根结点是否相同。
②合并两个集合：在①中已经获得两个元素的根结点faA和faB，因此只要把其中一个的父亲结点指向另一个结点，例如father[faA]=faB或者father[faB]=faA。

void Union(int a,int b)
{
    int faA=findFather(a); //查找a的根结点，记为faA
    int faB=findFather(b); //查找b的根结点，记为faB
    if(faA!=faB){          //不属于同一个集合
        father[faA]=faB;   //合并它们
    }
}

 

4、路径压缩

把当前查询结点的路径上的所有结点的父亲都指向根结点，查询复杂度降为O(1)
思路：
①按原先的写法获得x的根结点r
②重新从x开始走一遍寻找根结点的过程，把路径上经过的所有结点的父亲全部改为根结点r

int findFather(int x){
    //由于x在下面的while种会变成根结点，因此先把原先的x保存一下
    int a=x;
    while(x!=father[x]){    //寻找根结点
        x=father[x];
    }
    //到这里，x存放的是根结点，下面吧路径上的所有结点的father都改为根结点
    while(a!=father[a])
    {
        int z=a;         //因为a要被father[a]覆盖，所以先保存a的值，以修改father[a]
        a=father[a];     //a回溯父亲结点
        father[z]=x;     //将原先的结点a的父亲结点改为根结点x
    }
    return x;            //返回根结点
}

递归写法

int findFather(int v){
    if(v==father[v]) return v;    //找到根结点
    else{
        int F=findFather(father[v]);  //递归寻找father[v]的根结点
        father[v]=F;      //将根结点F赋值给father[v]
        return F;         //返回根结点F
    }
}

 

二、练习题

HDU 1856

题意：有编号为1到10^7的男生在一个房间，现在给出n组数据，每组数据包括两个编号，且这两个编号的人是朋友，如果A和B是朋友，B和C是朋友，那么A,B,C三人都是朋友，哪一个朋友圈中人数最多，输出这个朋友圈的人数;

 思路：并查集思想，多个集合中元素最多的即为所求；可看做求每个集合的元素数目，这里借助num数组，存储以该结点作为根结点时的集合元素总数，初始值均为1，可看做每个元素最初单独构成一个集合，在合并两个不在同一集合的元素时，更新根结点的num值，并比较更新后的num值和maxm，maxm总是取当前各个集合元素的最大值。最后输出maxm即为所求。这里数据量较大，容易时间超限，故用路径压缩；

#include 
#include 
using namespace std;
#define maxn 10000005
int father[maxn],num[maxn],maxm;
void Initial()
{
    for(int i=1;i<=maxn;i++){
        father[i]=i;
        num[i]=1;
    }
}
int findFather(int x)
{
    int a=x;
    while(x!=father[x])
    {
        x=father[x];
    }
    //路径压缩
    while(a!=father[a])
    {
        int d=a;
        a=father[a];
        father[d]=x;
    }
    return x;
}
void Union(int a,int b)
{
    int faA=findFather(a);
    int faB=findFather(b);
    if(faA!=faB){
        father[faA]=faB;
        num[faB]+=num[faA];
        maxm=max(maxm,num[faB]);   
    }
}
int main()
{
    int n,var1,var2;
    while(cin>>n)
    {
        Initial();
        maxm=0;
        if(n==0){
            printf("1\n");
            continue;
        }
        for(int i=0;i)
        {
            scanf("%d %d",&var1,&var2);
            Union(var1,var2);
        }
        cout<endl;
    }
    return 0;
}

问题 A: 通信系统

题目描述

某市计划建设一个通信系统。按照规划，这个系统包含若干端点，这些端点由通信线缆链接。消息可以在任何一个端点产生，并且只能通过线缆传送。每个端点接收消息后会将消息传送到与其相连的端点，除了那个消息发送过来的端点。如果某个端点是产生消息的端点，那么消息将被传送到与其相连的每一个端点。
为了提高传送效率和节约资源，要求当消息在某个端点生成后，其余各个端点均能接收到消息，并且每个端点均不会重复收到消息。
现给你通信系统的描述，你能判断此系统是否符合以上要求吗？

输入

输入包含多组测试数据。每两组输入数据之间由空行分隔。
每组输入首先包含2个整数N和M，N（1<=N<=1000）表示端点个数，M（0<=M<=N*(N-1)/2）表示通信线路个数。
接下来M行每行输入2个整数A和B（1<=A，B<=N），表示端点A和B由一条通信线缆相连。两个端点之间至多由一条线缆直接相连，并且没有将某个端点与其自己相连的线缆。
当N和M都为0时，输入结束。

输出

对于每组输入，如果所给的系统描述符合题目要求，则输出Yes，否则输出No。

样例输入 http://codeup.cn/problem.php?cid=100000615&pid=1

#include 
#include 
#include <set>
using namespace std;
#define maxn 1005
int father[maxn];
void Initial(int n)
{
    for(int i=1;i<=n;i++) father[i]=i;
}
int findFather(int x)
{
    int a=x;
    while(x!=father[x]){
        x=father[x];
    }
    while(a!=father[a])
    {
        int z=a;
        a=father[a];
        father[z]=x;
    }
    return x;
}
void Union(int a,int b)
{
    int faA=findFather(a);
    int faB=findFather(b);
    if(faA!=faB){
        father[faA]=faB;
    }
}
int main()
{
    int n,m;
    int var1,var2;
    while(cin>>n)
    {
        if(n==0) break;
        cin>>m;
        set<int> st;
        Initial(maxn);
        for(int i=0;i)
        {
            cin>>var1>>var2;
            Union(var1,var2);
        }
        for(int i=1;i<=n;i++)
        {
            findFather(i);
            st.insert(father[i]);
        }
        cout<1<<endl;
    }
    return 0;
}

 

问题C:How Many Tables

http://codeup.cn/problem.php?cid=100000615&pid=2

#include 
#include 
#include <set>
using namespace std;
#define maxn 1005
int father[maxn];
void Initial(int n)
{
    for(int i=1;i<=n;i++) father[i]=i;
}
int findFather(int x)
{
    int a=x;
    while(x!=father[x]){
        x=father[x];
    }
    while(a!=father[a])
    {
        int z=a;
        a=father[a];
        father[z]=x;
    }
    return x;
}
void Union(int a,int b)
{
    int faA=findFather(a);
    int faB=findFather(b);
    if(faA!=faB){
        father[faA]=faB;
    }
}
int main()
{
    int n,m,t;
    int var1,var2;
    cin>>t;
    while(t>0)
    {
        cin>>n>>m;
        set<int> st;
        Initial(maxn);
        for(int i=0;i)
        {
            cin>>var1>>var2;
            Union(var1,var2);
        }
        for(int i=1;i<=n;i++)
        {
            findFather(i);
            st.insert(father[i]);
        }
        cout<endl;
        t--;
    }
    return 0;
}