【C/C++】并查集

并查集操作的简单实现

• 原理：定义一个数组s[i]来表示第i个元素属于哪个集团，因此初始化时s[i] = i；即每个元素都还是分散的。对于可以合并的两个元素x与y，查找到他们两个所属的集团，将其中一个合并到另一个即可；
• 代码实现：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e4 + 10;
int s[maxn];

void init_set(int n)
{
    for(int i=1; i<=n; i++)
        s[i] = i;
}

int find_set(int x)//查询x的集团编号
{
    return s[x] == x?x:find_set(s[x]);
}

void union_set(int x, int y)
{
    x = find_set(x);
    y = find_set(y);
    if(x != y) s[x] = s[y];
}

int main()
{
    int n,m,x,y;
    while(~scanf("%d %d",&n,&m))
    {
        init_set(n);//初始化
        for(int i=0; i<m; i++)
        {
            scanf("%d %d",&x,&y);
            union_set(x, y);//将x的集团与y的集团合并
        }
        int ans = 0;
        for(int i=1; i<=n; i++)//统计有多少个集团
            if(s[i] == i)
                ans++;
        printf("%d\n",ans);
    }
    return 0;
}

合并的优化

• 将两个集团合并时，可以看做是两个树的合并，而高度较小的树合并到较大的树上可以使树的高度不变。引入一个数组height[i]来表示树的高度即可
• 代码实现：

void init_set(int n)
{
    for(int i=1; i<=n; i++)
    {
        s[i] = i;
        height[i] = 0;
    }
}

void union_set(int x, int y)
{
    x = Find_set(x);
    y = Find_set(y);
    if(height[x] == height[y])
    {
        height[x]++;
        s[y] = x;
    }
    else
    {
        if(height[x] > height[y]) 
            s[y] = x;
        else 
            s[x] = y;
    }
}

查询的优化

• 每次搜索的过程中，如果顺便将i所属的集团改为根节点，再次查找i的时候就可以直接返回结果了
• 代码实现

//递归查询，容易爆栈
int find_set(int x)
{
    if(x != s[x]) 
        s[x] = find_set(s[x]);
    return s[x];
}

//非递归查询
int Find_set(int x)
{
    int r = x;
    while(r != s[r]) r = s[r];
    int i=x,j;
    while(i != r)
    {
        j = s[i];
        s[i] = r;
        i = j;
    }
    return r;
}