原理
在一些应用问题中，需要将n个不同的元素划分成一些不相交集合。
开始时，每个元素自成一个单元素集合，然后按照一定的规律将归于同一组的元素合并。在此过程中要反复用到查询某一个元素归属于哪个集合的运算。
初始状态
初始状态下，有九个元素，自成一个集合。
其中有三个分组：{0,6,7,8} {1,4,9}{2,3,5}
我们设置0,1,2为根节点：
数组表示为如下所示：
其中：
- 数组的下标对应集合中元素编号
- 数组元素如果为负数，则该节点为根节点，绝对值指该集合中元素的个数
- 数组中如果为非负数，则代表该元素的父亲在数组的下标
我们将{1,4,9}集合并入{0,6,7,8}集合
总结一下可以解决的问题：
- 查找元素属于哪个集合
- 查看两个元素是否属于同一集合
- 将两个集合归并成一个集合
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class UnionFindset
{
public:
UnionFindset(size_t size) : _ufs(size, -1) {}
int FindRoot(int index)
{
while (_ufs[index] >= 0)
{
index = _ufs[index];
}
return index;
}
bool Union(int x1, int x2)
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
if (root1 == root2)
return false;
_ufs[root1] += _ufs[root2];
_ufs[root2] = root1;
return true;
}
size_t Count() const
{
size_t count = 0;
for (auto e : _ufs)
{
if (e < 0)
count++;
}
return count;
}
int &operator[](int index)
{
if (index >= _ufs.size())
{
_ufs.resize(_ufs.size() * 2);
}
return _ufs[index];
}
private:
vector<int> _ufs;
};
int main()
{
UnionFindset u(10);
u[0] = -4;
u[1] = -3;
u[2] = -3;
u[3] = 2;
u[4] = 1;
u[5] = 2;
u[6] = 0;
u[7] = 0;
u[8] = 0;
u[9] = 1;
int index = u.FindRoot(8);
cout << index << endl;
cout << u.Count() << endl;
bool ans = u.Union(1, 8);
cout << ans << endl;
cout << u.Count() << endl;
system("pause");
return 0;
}
|
例题
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| #include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <deque>
using namespace std;
void PrintVector2D(const vector<vector<int>> &array)
{
for (const auto &row : array)
{
cout << "[";
for_each(row.begin(), row.end(), [](int num)
{ cout << num << " "; });
cout << "]";
cout << endl;
}
}
struct ListNode
{
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(nullptr), right(nullptr) {}
};
class Solution
{
public:
int findCircleNum(vector<vector<int>> &isConnected)
{
vector<int> ufs(isConnected.size(), -1);
auto findRoot = [&ufs](int x)
{
while (ufs[x] >= 0)
{
x = ufs[x];
}
return x;
};
for (size_t i = 0; i < isConnected.size(); i++)
{
for (size_t j = 0; j < isConnected[i].size(); j++)
{
if (isConnected[i][j] == 1)
{
int root1 = findRoot(i);
int root2 = findRoot(j);
if (root1 != root2)
{
ufs[root1] += ufs[root2];
ufs[root2] = root1;
}
}
}
}
int n = 0;
for (auto e : ufs)
{
if (e < 0)
++n;
}
return n;
}
};
int main()
{
Solution s;
vector<vector<int>> isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
int x = s.findCircleNum(isConnected);
cout << x << endl;
system("pause");
return 0;
}
|
