【面试题】例如已知有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[])
java:
int friends(int n, int m, int [][] r)
分析：可能大家会想到用数组统计存在好友关系的人名，但此方法对于好友关系复杂，人数较多时，效率较低。我们可以通过并查集思进行实现。
并查集：
（1）将N个不同的元素分成一组不相交的集合。
（2）开始时，每个元素就是一个集合，然后按规律将两个集合进行合并。
例如下图：
具体实现如下：
#pragma once
class UnionSet
{
public:
UnionSet()
:_set(NULL)
, _n(0)
{}
UnionSet(size_t size)
:_set(new int(size))
, _n(size)
{
size_t i = 0;
for (; i < size; ++i)//初始化数组为-1
{
_set[i] = -1;
}
_set[i] = '\0';
}
void Union(int root1, int root2)//root1和root2是好友,以一个人为这个朋友圈的核心，找到与其相关的朋友
{
assert(_set[root1] < 0);
assert(_set[root2] < 0);
_set[root1] += _set[root2];
_set[root2] = root1;
}
size_t FindRoot(int root)//找到root所属的这个朋友圈的核心，
{
while (_set[root] >= 0)//说明不是朋友圈的根结点
{
root = _set[root];//向朋友圈的上一级找，直到为负数结束
}
return root;
}
void Count()
{
int count = 0;
for (size_t i = 0; i < _n; ++i)
{
if (_set[i] < 0)
count++;
}
cout << count << endl;
}
private:
int* _set;
size_t _n;
};
size_t Find(int* a, int root)
{
assert(a);
while (a[root] >= 0)
root = a[root];
return root;
}
int FindFriends(int n, int m, int r[][2])//n个人，m对好友关系，r[][2]二维数组表示关系的两个人
{
int* a = new int[n];
for (size_t i = 0; i < n; ++i)//初始化数组
{
a[i] = -1;
}
int root1 = 0, root2 = 0;
for (size_t i = 0; i < m; ++i)
{
root1 = Find(a, r[i][0]);//找根
root2 = Find(a, r[i][1]);
if (root1 != root2)
{
a[root1] += a[root2];
a[root2] = root1;
}
}
int count = 0;
for (size_t i = 0; i < n; ++i)
{
if (a[i] <= 0)
count++;
}
return count;
}
void UnionSetTest()
{
UnionSet us(10);
us.Union(0, 6);
us.Union(0, 7);
us.Union(0, 8);
us.Union(1, 4);
us.Union(1, 9);
us.Union(2, 3);
us.Union(2, 5);
cout << us.FindRoot(9) << endl;
us.Count();//朋友圈的个数
int r[8][2] = { { 1, 4 }, { 1, 9 }, { 2, 3 }, { 2, 5 }, { 0, 6 }, { 0, 7 }, { 0, 8 }, { 8, 9 } };
cout << FindFriends(10, 7, &r[0]) << endl;
}
不用类进行实现，如下所示
#include<assert.h>
size_t Find(int* a, int root)
{
assert(a);
while (a[root] >= 0)
root = a[root];
return root;
}
int FindFriends(int n, int m, int r[][2])//n个人，m对好友关系，r[][2]二维数组表示关系的两个人
{
int* a = new int[n];
for (size_t i = 0; i < n; ++i)//初始化数组
{
a[i] = -1;
}
int root1 = 0, root2 = 0;
for (size_t i = 0; i < m; ++i)
{
root1 = Find(a, r[i][0]);//注意找根
root2 = Find(a, r[i][1]);
if (root1 != root2)
{
a[root1] += a[root2];
a[root2] = root1;
}
}
int count = 0;
for (size_t i = 0; i < n; ++i)
{
if (a[i] < 0)
count++;
}
return count;
}
void FriendsTest()
{
int r[8][2] = { { 1, 4 }, { 1, 9 }, { 2, 3 }, { 2, 5 }, { 0, 6 }, { 0, 7 }, { 0, 8 }, { 8, 9 } };
cout << FindFriends(10, 8, &r[0]) << endl;
}