假如已知有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个朋友圈。
这个问题可以通过数据结构中的并查集来实现。
并查集
将N个不同的元素分成一组不相交的集合。
开始时，每个元素就是一个集合，然后按规律将两个集合合并。
代码如下：
UnionFindSet.h：
计算
安全
数据库
网络和加速
企业服务
#pragma once
class UnionFindSet
{
public:
UnionFindSet(int N)
:_a(new int[N])
,_n(N)
{
memset(_a, -1, N * 4);//将每一组初始的元素值设为-1
}
//找该元素的根
int FindRoot(int x)
{
while (_a[x] >= 0)
{
x = _a[x];
}
return x;
}
//合并
void Union(int x1, int x2)
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
_a[root1] += _a[root2];//将元素2的根合并到元素1的根上
_a[root2] = root1;//元素2的值设置为元素1
}
//合并后集合总数
int Count()
{
int count = 0;
for (size_t i = 0; i < _n; ++i)
{
if (_a[i] < 0)
{
++count;
}
}
return count;
}
protected:
int* _a;//元素集合
size_t _n;//元素个数
};#include <iostream>
using namespace std;
#include "UnionFindSet.h"
int GroupsOfFriends(int n, int m, int r[][2])
{
UnionFindSet ufs(n+1);
for (size_t i = 0; i < m; ++i)
{
int x1 = r[i][0];
int x2 = r[i][1];
ufs.Union(x1, x2);
}
return ufs.Count()-1;//元素集合从0开始，应减去0的集合
}
void Test()
{
int r[][2] = {{1,2}, {1,3}, {4,5}};
int count = GroupsOfFriends(5, 3, r);
cout<<count<<endl;
}
int main()
{
Test();
return 0;
}
过程：
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
