并查集（UnionFindSet）

 小米的校招题：
朋友圈（25分）
假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友...），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。
假如：n = 5 ， m = 3 ， r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。
最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。
C/C++：
int friends(int n , int m , int* r[]);

思路：此题可以用并查集来解决，并查集数组刚开始里面存的都是-1，把每个圈子看成一个树，把其非根结点的-1都加到根节点里面去，然后非根节点存上根节点的下标，这样遍历数组时，为负数的就是根，负几那个朋友圈就有几个人，那几个人就是存这个根下标的元素。
具体实现如下：

#include<iostream>
#include<cassert>
using namespace std;

int FindRoot(int *set,int child)
{
    assert(set);
    while(set[child] >= 0)
    {
        child = set[child];
    }
    return child;
}
void Combine(int *set,int root1,int root2)
{
    assert(set);
    set[root1] += set[root2];
    set[root2] = root1;
}
int FindFrinedsCircle(int n,int m,int r[][2])
{
    assert(r);

    int *set = new int(n);
    memset(set,-1,sizeof(int)*n);

    for(int i = 0;i < m;++i)
    {
        int first = r[i][0];
        int second = r[i][1];

        int root1 = FindRoot(set,first);
        int root2 = FindRoot(set,second);

        if(root1 != root2)
        {
            Combine(set,root1,root2);
        }
    }
    int count = 0;
    for(int i = 0;i < n;++i)
    {
        if(set[i] < 0 )
        {
            count++;
        }
    }
    return count;
}
int main()
{
    int r[][2] = {{1 , 2} , {2 , 3} , {4 , 5}};
    cout<<FindFrinedsCircle(5,3,r)<<endl;
    return 0;
}