【数据结构】并查集

  先看一道题:假如已知有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个朋友圈。
  
  第一种方法:我们可以创建3个set——s1,s2,s3对应3对关系,分别在s2和s3中查找s1中的0和1,如果找到了,将s2中的元素插入s1中,并清空s2;统计非空set的个数,即可得到朋友圈的个数。

什么是并查集?


  并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。并查集是一种树型的数据结构,用于处理一些不想交的集合的合并及查询问题。在使用中,常常以森林来表示。
  每一个集合以一颗树来表示,树的每一个结点代表集合的一个元素,开始时,每个元素是一个自己的集合,因此是一个森林。类似堆,我们用一个数组的下标表示元素名,第i个数组元素代表它所在的集合的根结点。树的根结点的下标代表集合名称,根结点的值表示集合中元素个数。

主要操作有:

  1. 初始化:这一步通常只执行一次
  2. 查找:查找元素所在的集合,即根结点
  3. 合并:将两个元素所在的集合合并​

举一个例子:
假设一个集合s为:s={0,1,2,3,4,5,6,7,8,9}。
1》初始化:我们全部用-1初始化每一个树的根结点
这里写图片描述

0 1 2 3 4 5 6 7 8 9
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

2》合并成以下3个集合:
s1={0,3,4,5,6}; s2={1,7,8}; s3={2,9};
其树形结构如下:
这里写图片描述
按照上面树的结构,假设我们的数组名为a,我们需要执行的操作是,a[0]=a[0]-a[3](因为是负数,所以需要减操作); a[3]=0(3的父结点);
以此类推,我们可以得到这样的数组:

0 1 2 3 4 5 6 7 8 9
-5 -3 -2 0 0 0 0 1 1 2

我们可以发现,数组中的负数的绝对值表示的是集合中元素的个数;负数的个数表示集合的个数;非负的数字表示的其下标对应的父结点。

3》假如要将6对应的集合与9对应的集合合并。应该怎么做?
这里写图片描述
首先,判断6和9对应的父结点是不是同一个结点,如果是同一个,则说明他们本身就在同一个集合中;如果不是同一个,则先找到6和9的父结点——0和2,再执行a[0]=a[0]-a[2]; a[2]=0(2的父结点);
此时数组变为:

0 1 2 3 4 5 6 7 8 9
-7 -3 0 0 0 0 0 1 1 2

并查集的代码如下

#include <iostream>
#include <vector>
using namespace std;
class UnionFind
{
public:
     UnionFind(size_t size)
          : _set(size, -1)//构造函数
     {
          // _set.resize(size, -1);//用-1初始化 3中方法都可以实现
          // _set.assign(size, -1);
     }
     void Union(int x1, int x2)
     {
          int root1 = FindRoot(x1);
          int root2 = FindRoot(x2);
          if (root1 != root2)
          {
               _set[root1] += _set[root2];
               _set[root2] = root1;
          }
     }
     size_t Count()// 合并后的个数
     {
          size_t count = 0;
          for (size_t i = 0; i < _set.size(); i++)
          {
               if (_set[i] < 0)
                    count++;
          }
          return count;
     }
private:
     int FindRoot(int x)// 查找父结点
     {
          while (_set[x] >= 0)
               x = _set[x];
          return x;
     }
private:
     vector<int> _set;
};

此时,再来看我们开头提的问题,就会变得很简单了:

size_t friends(const int n, const int m, int r[][2])
{
     UnionFind u(n + 1);//根据题目给出的编号,为方便解决题目,所以没有使用0号位置
     for (int i = 0; i < m; i++)
          u.Union(r[i][0], r[i][1]);
     return u.Count() - 1;//因为0号位置没有使用,而初始化的-1为负数,所以要减1
}
int main()
{
     const int m = 3;
     const int n = 5;
     int r[3][2] = { { 1, 2 }, { 2, 3 }, { 4, 5 } };
     cout << "朋友圈个数:" << friends(n, m, r) << endl;
     return 0;
}

运行结果:
这里写图片描述

相关文章
相关标签/搜索