并查集

并查集

并查集算法实际上是找不相交的集合的算法。
例如：有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（树根），即有几个朋友圈。

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