【数据结构】并查集

　　先看一道题：假如已知有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,3,4,5,6,7,8,9}。
1》初始化：我们全部用-1初始化每一个树的根结点

2》合并成以下3个集合：
s1={0,6}; s2={1,8}; s3={2,9};
其树形结构如下：

按照上面树的结构，假设我们的数组名为a，我们需要执行的操作是，a[0]=a[0]-a[3](因为是负数，所以需要减操作); a[3]=0(3的父结点);
以此类推，我们可以得到这样的数组：

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

3》假如要将6对应的集合与9对应的集合合并。应该怎么做？

首先，判断6和9对应的父结点是不是同一个结点，如果是同一个，则说明他们本身就在同一个集合中；如果不是同一个，则先找到6和9的父结点——0和2，再执行a[0]=a[0]-a[2]; a[2]=0(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;
}

运行结果：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!