C++实现并查集-创新互联

假如已知有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;//元素个数
};

Test.cpp

#include 
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<
过程：
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
            

            本文名称：C++实现并查集-创新互联            

            URL分享：http://cdkjz.cn/article/dipcpj.html