数据结构——并查集

目录
一并查集原理
二并查集实现
 三并查集应用
省份数量
等式方程的可满意性

---

一并查集原理

在一些应用问题中，必要将n个不同的元素划分成不相交的集合；                                                 开始时，每个元素自成一个单元素集合，然后按肯定的规律将不同集合举行合并；                        在此过程中要查询某一个元素归属于那个集合的运算。这类问题可以用并查集来办理
好比：某公司今年校招全国总共招生5人，西安招2人，成都招3人；5个人来自不同的学校，起先互不相识，每个学生都是一个独立的小团体；                                                       
现给这些学生举行编号：{0, 1, 2, 3,4}; (-1代表在该集合中只有自己一人)

毕业后，学生们要去公司上班，每个地方的学生自发组织成小分队一起上路，于是：
西安学生小分队s1={0,1}，成都学生小分队s2={2,3,4}，各自形成一个小团体：

   每棵树的根/每个集合的第一个数存的是集合的个数(为了与编号区别开存的是相反数)，而在集合内的别的数则存的是第一个数的编号(通常是下标)
  通过平常的相处，2号与1号渐渐熟悉成为了朋友，此时这两个集合就可以合并成一起，成为一个新的集合：（哪个集合合并哪个集合随意，没规定）

 
   总结：
  1. 数组的下标对应集合中元素的编号；
2. 数组的值中如果为负数，负号代表根，数字代表该集合中元素个数；
3. 数组的值中如果为非负数，代表该元素双亲在数组中的下标（编号）
  二并查集实现

创建一个并查集对象通常必要根据传过来的数据个数举行开发空间并初始化成-1；实现时可以用vector来接收；（如果传过来是别的数据，我们就要在内部对数据举行编号）
   并查集实现一般实现四个功能接口：
  1找根；2合并两个集合；3判断是否在同一个集合；4.当前集合的个数

1. #include <iostream>
2. #include <vector>
3. #include <unordered_map>
4. using namespace std;
6. // 如果是其它数据的话要自己建立映射
7. //  template <class T>
8. //  class UnionFindSet
9. //  {
10. //  public:
11. //      UnionFindSet(const vector<T> &v)
12. //      {
13. //          for (int i = 0; i < v.size(); i++)
14. //          {
15. //              _v.push_back(v[i]);
16. //              _ufs[v[i]] = i;
17. //          }
18. //      }
20. // private:
21. //     vector<T> _v;               // 值映射下标
22. //     unordered_map<T, int> _ufs; // 下标找值
23. // };
25. template <class T>
26. class UnionFindSet
27. {
28. public:
29.     UnionFindSet(int size)
30.     {
31.         _ufs.resize(size, -1);
32.     }
33.     // 找根
34.     int FindSet(int x)
35.     {
36.         int root = x;
37.         while (_ufs[root] >= 0)
38.         {
39.             root = _ufs[root]; // 更新根，一定注意不要写错
40.         }
41.         return root;
42.     }
43.     // 合并集合
44.     void UnionSet(int x, int y)
45.     {
46.         int root1 = FindSet(x);
47.         int root2 = FindSet(y);
48.         if (root1 != root2)
49.         {
50.             _ufs[root1] += _ufs[root2];
51.             _ufs[root2] = root1;
52.         }
53.     }
54.     // 是否在同一集合
55.     bool IsSet(int x, int y)
56.     {
57.         return FindSet(x) == FindSet(y);
58.     }
59.     // 当前集合个数
60.     int Size()
61.     {
62.         int n = 0;
63.         for (auto e : _ufs)
64.         {
65.             if (e < 0) // n-=e;
66.                 ++n;
67.         }
68.         return n;
69.     }
71. private:
72.     vector<T> _ufs;
73. };

复制代码

 三并查集应用

省份数量

有了上面实现，办理该题不是轻而易举吗！

1. #include <iostream>
2. #include <vector>
3. using namespace std;
5. template <class T>
6. class UnionFindSet
7. {
8. public:
9.     UnionFindSet(int size)
10.     {
11.         _ufs.resize(size, -1);
12.     }
14.     int FindSet(int x)
15.     {
16.         int root = x;
17.         while (_ufs[root] >= 0)
18.         {
19.             root = _ufs[root];
20.         }
21.         return root;
22.     }
24.     void UnionSet(int x, int y)
25.     {
26.         int root1 = FindSet(x);
27.         int root2 = FindSet(y);
28.         if (root1 != root2)
29.         {
30.             _ufs[root1] += _ufs[root2];
31.             _ufs[root2] = root1;
32.         }
33.     }
35.     bool IsSet(int x, int y)
36.     {
37.         return FindSet(x) == FindSet(y);
38.     }
40.     int Size()
41.     {
42.         int n = 0;
43.         for (auto e : _ufs)
44.         {
45.             if (e < 0) // n-=e;
46.                 ++n;
47.         }
48.         return n;
49.     }
51. private:
52.     vector<T> _ufs;
53. };
55. class Solution
56. {
57. public:
58.     int findCircleNum(vector<vector<int>> &isConnected)
59.     {
60.         UnionFindSet<int> ufs(isConnected.size());
61.         for (int i = 0; i < isConnected.size(); i++)
62.         {
63.             for (int j = 0; j < isConnected[i].size(); j++)
64.             {
65.                 if (isConnected[i][j] == 1)
66.                 {
67.                     ufs.UnionSet(i, j);
68.                 }
69.             }
70.         }
71.         return ufs.Size();
72.     }
73. };

复制代码

等式方程的可满意性

   先遍历一遍：相等的字符存在同一个集合中；
  再遍历一遍：两个不相等的字符去并查集找是否在同一个集合中，是返回false；
  留意：办理该问题并不愿定每次都要把并查集实现一遍：实现出我们想要的函数即可

1. class Solution
2. {
3. public:
4.     bool equationsPossible(vector<string> &equations)
5.     {
6.         vector<int> ufs(26, -1);
8.         auto Find = [&ufs](int x)
9.         {
10.             while (ufs[x] >= 0)
11.                 x = ufs[x]; // 注意这里的逻辑!
12.             return x;
13.         };
15.         for (auto &equation : equations)
16.         {
17.             if (equation[1] == '=')
18.             {
19.                 int root1 = Find(equation[0] - 'a'), root2 = Find(equation[3] - 'a');
20.                 if (root1 != root2)
21.                 {
22.                     ufs[root1] += ufs[root2];
23.                     ufs[root2] = root1; // 这里也要赋值对
24.                 }
25.             }
26.         }
28.         for (auto &equation : equations)
29.         {
30.             if (equation[1] == '!')
31.             {
32.                 int x = Find(equation[0] - 'a');
33.                 int y = Find(equation[3] - 'a');
34.                 if (x == y)
35.                     return false;
36.             }
37.         }
38.         return true;
39.     }
40. };

复制代码

   以上便是全部内容，有问题欢迎在评论区指正，感谢观看！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。