欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

并查集

程序员文章站 2022-07-12 23:39:21
...

并查集

并查集算法实际上是找不相交的集合的算法。
例如:有n个人,m种关系,如果a认识b,b认识c,那么a能通过b认识c,最后能有几个朋友圈。
刚开始时,每个人都是独立的,假如有总共有五个人,建立一个一维数组s[6](需要进行初始化),s[1]~s[5]分别表示这五个人,数组的下标分别代表他们朋友圈中的那个“boss”,通过给出的关系,来合并朋友圈。
假设每个人最开始的“boss”是自己,s[1]~s[5]的值等于它的boss是谁,它们最开始的值等于他们的下标。
样例输入:
9 8
1 2
3 4
5 2
4 6
2 6
9 7
8 7
1 6
样例输出:
2
通过给出的关系合并朋友圈,第一组中,1和2是朋友,根据“靠左”法则,2的boss是1,那么s[2]的值变为1。相同的,第二组中,3和四是朋友,所以s[4]的值变为3。
而第三组中,5和2是朋友,这时关系发生冲突,将5就变成了1和2的boss,s[5]=s[1]=s[2]=5,这样就保留了之前的关系。第四组中s[4]=s[6]=4,第五组中,s[2]=s[5]=s[1]=s[6]=5,第六组中,s[9]=s[7]=9,
第七组中,s[8]=s[7]=s[9]=8,第八组中,s[1]=s[5]=s[2]=s[6]=s[4]=5。
所以这个过程就是找boss,找到树的根结。

最开始时,他们的boss都是自己。

void init()
{
    int i;
    for(i=1;i<=n;i++)
        s[i]=i;//s[i]的值就代表它的boss是谁
    return ;
}

第二步,合并朋友圈

void merge( int x, int y)
{
     int n1=fun(x),n2=fun(y);
    if(n1==n2)
        return ;
    s[n2]=n1;
}

第三步,找到朋友圈中的boss(树根)

int fun(lnt a)
{
    if(s[a]!=a)
    {
        s[a]=fun(s[a]);
        return s[a];
    }
    else
        return a;
}

结束后,再将整个数组循环一遍,找出有几个boss(树根),即有几个朋友圈。

并查集也是树的结构, 通过复杂的关系找树根, 确定有几个不相交的集合。

相关标签: 每日一题