【数据结构】朋友圈问题的解决——并查集

3/8/2017来源:ASP.NET技巧人气:1242

本篇博文旨在介绍一种数据结构——并查集;本文介绍了该数据结构的使用场景,并用代码进行了实现该数据结构

朋友圈问题:

1、已知,有n个人和m对好友关系(存于一个集合r中)

2、如果两个人是直接的或者间接的好友(好友的好友的好友。。。),那么他们属于一个集合,就是一个朋友圈里的

3、写出程序,求这n个人中一共有多少个朋友圈

文字描述还不明白的童鞋,可以看下面这个例子

例如:

n = 5 m = 3   

r = { { 1 , 2 },{ 2 , 3 },{ 4 , 5 } }

五个人有三对朋友关系

根据 集合r  我们可以看出1 、 2 、3 属于一个朋友圈,4和5属于一个朋友圈

所以结果有两个朋友圈

由于之前学习过哈希表

所以就想出了这样的解法

建立一个长度为n+1的数组(可以利用vector)

对应下标代表的是该人

然后遍历一遍 集合r  比如(1,2)就将2挂到1节点的后面

最后我们遍历一遍该数组,从1链接的节点中找到2,然后去找下标为2的数组链接的数字3,再找3,然后3没有链接节点,则表示是一个朋友圈

依次轮推,可以算出两个朋友圈

这个方法的确可行

但是,当关系量稍微复杂点就不好使了

其实7个人同属于一个朋友圈,但是1-2结束,就多算一个朋友圈

而且,由于处理不当还出现了循环的问题,比如1-2-3-1

当然,这种情况可以通过加以处理来避免

但是这样也太复杂了

有没有一种简便的方法来处理这个问题呢?

这里引入这次要介绍的数据结构——并查集

并查集

基本概念

将N个不同的元素分成互不相交的集合

然后按照规律将两个集合进行合并

基本思想

1、首先我们建立n个大小的数组,分别代表人的序号

将数组的所有值初始化为 -1 ,代表各自属于各自的集合

2、根据 集合r 对数组元素的值进行修改

比如 {0,6}

将a[0] 的值加上 a[6]的值

然后将a[6]所存的值改为 a[0]的下标 0 

修改后的下标如下图所示

下面,如果0和4产生了关系,{0,4}

那么找到4的根(为1),将a[1]的值加到a[0]上,然后将a[1]的值改为a[0]的下标0

通过对数组元素的遍历,只要值小于0,即代表为一个集合(朋友圈)中

代码实现

#PRagma once

#include<iostream>
using namespace std;

#include<vector>

//定义并查集
class UnionFindSet
{
public:
	//构造函数,将初始值置为-1
	//并进行扩容
	UnionFindSet(size_t n)
	{
		v.resize(n+1, -1);
	}

	//找到根节点
	size_t FindRoot(size_t x)
	{
		size_t ret = x;

		while (v[ret] >= 0)
			ret = v[ret];

		return ret;
	}

	//将两个人的朋友圈进行合并
	void Union(size_t x1,size_t x2)
	{
		size_t root1 = FindRoot(x1);
		size_t root2 = FindRoot(x2);

		//同根,已经在一个集合
		if (root1 == root2)
			return;

		v[root1] += v[root2];
		v[root2] = root1;
	}

	//判断是否在一个集合
	bool IsInSet(int x1, int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}

	//求集合(朋友圈)的个数
	size_t SetSize()
	{
		size_t count = 0;
		for (size_t i = 0; i < v.size(); ++i)
		{
			if (v[i] < 0)
				count++;
		}

		return count-1;
	}
protected:
	vector<int> v;
};

void TestUnionFindSet()
{
	//五个人,四个人有朋友圈关系
	const int n = 5;
	const int m = 4;

	UnionFindSet ufs(n);
	int r[m][2] = { { 1, 2 }, { 2, 3 }, { 4, 5 }, { 2, 4 } };
	for (size_t i = 0; i < m; ++i)
	{
		ufs.Union(r[i][0], r[i][1]);
	}

	cout << "朋友圈的个数为:" << ufs.SetSize() << endl;
}

代码的GitHub链接

https://github.com/haohaosong/DataStruct/blob/master/UnionFindSet.h