剑指offer（专项突破版）15.4 并查集
并查集是一种树形的数据结构，用来表示不相交集合的数据。并查集中的每个子集是一棵树，每个元素是某棵树中的一个节点。树中的每个节点有一个指向父节点的指针，树的根节点的指针指向它自己。并查集支持两种操作，即合并和查找。合并操作将两个子集合并成一个集合，只需要将一个子集对应的树的根节点的指针指向另一个子集对应的树的根节点。另一种操作是查找，即确定某个元素v处于哪个子集中。并查集中的子集由对应的树的根节点代表。从元素v对应的节点开始沿着指向父节点的指针一直找到树的根节点，即节点的祖先节点。并查集的查找操作经常用来判断两个元素是否属于同一个子集。如果两个元素的祖先节点相同，那么它们属于同一个子集。
并查集经常用来解决图的动态连接问题。假设一个图中有n个节点，最开始的时候这n个节点互不连通，形成n个只有一个节点的子图。每次从图中选取两个节点，如果这两个节点不在同一个子图中，添加一条边连接这两个节点，那么它们所在的子图也就连通了。在添加m条边之后，这个图中子图的数目是多少？最大的子图有多少个节点？这类问题都可以用并查集解决。图中的每个子图对应并查集中的子集，判断图中的两个节点是否在同一个子图就是判断它们对应的元素是否在并查集的同一个子集中，连通图中的两个子图就是合并并查集中的两个子集。
图搜索
一个班级可以包含一个或多个朋友圈，对应的图中可能包含一个或多个子图，每个朋友圈对应一个子图。因此，这个问题可以转化为如何求图中子图的数目。
图的搜索算法可以用来计算图中子图的数目。扫描图中所有的节点。如果某个节点v之前没有访问过，就搜索它所在的子图。当所有节点都访问完之后，就可以知道图中有多少个子图。
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
| class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
vector<bool> visited(n);
int res = 0;
for(int i = 0; i < n; i++){
if(!visited[i]){
findCircle(isConnected, visited, i);
res++;
}
}
return res;
}
void findCircle(vector<vector<int>>& isConnected, vector<bool>& visited, int i){
queue<int> que;
que.push(i);
while(!que.empty()){
int cur = que.front();
que.pop();
visited[cur] = true;
for(int j = 0; j < isConnected.size(); j++){
if(isConnected[cur][j] == 1 && !visited[j]){
que.push(j);
}
}
}
}
};
|
- 时间复杂度：$O(n^2)$
- 空间复杂度：O(n)
并查集
并查集的子集和图中的子图对应，并查集中的子集用树形结构表示。子集的节点都有父节点，根节点的父节点就是它自身。同一个子集中不同节点的根节点一定相同。判断两个节点是不是连通，也就是判断它们是不是属于同一个子集，只需要看它们的根节点是不是相同就可以。
创建长度为n的数组fathers存储n个节点的父节点。有了这个数组fathers，如果想知道节点i所在的子集的根节点，就可以从节点i开始沿着指向父节点的指针搜索，时间复杂度看起来是O（n），但可以将从节点i到根节点的路径压缩，从而优化时间效率。
我们真正关心的是节点i的根节点是谁而不是它的父节点，因此可以在fathers[i]中存储它的根节点。当第1次找节点i的根节点时，还需要沿着指向父节点的边遍历直到找到根节点。一旦找到了它的根节点，就把根节点存放到fathers[i]中。不仅如此，还可以一起更新从节点i到根节点的路径上所有节点的根节点。以后只需要O（1）的时间就能知道这些节点的根节点。这种优化叫作路径压缩，因为从节点i到根节点的路径被压缩成若干长度为1的路径。
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
| class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
vector<int> fathers(n);
for(int i = 0; i < n; i++){
fathers[i] = i;
}
int res = n;
for(int i = 0; i < n - 1; i++){
for(int j = i+1; j < n; j++){
if(isConnected[i][j] == 1 && unionFathers(fathers, i, j)){
res--;
}
}
}
return res;
}
int find(vector<int>& fathers, int x){
if (fathers[x] != x) {
fathers[x] = find(fathers, fathers[x]);
}
return fathers[x];
}
bool unionFathers(vector<int>& fathers, int x, int y){
int fx = find(fathers, x);
int fy = find(fathers, y);
if(fx != fy){
fathers[fx] = fy;
return true;
}
return false;
}
};
|
- 时间复杂度：$O(n^2)$
- 空间复杂度：O(n)
分析
函数similar用来判断两个字符串是否相似。由于题目假设输入的字符串为一组变位词，因此只要两个字符串之间对应位置不同字符的个数不超过两个，那么它们一定相似。
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
| class Solution {
public:
int numSimilarGroups(vector<string>& strs) {
int n = strs.size();
vector<int> fathers(n);
for(int i = 0; i < n; i++){
fathers[i] = i;
}
int res = n;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(isSimilar(strs[i], strs[j]) && unionStr(fathers, i, j)){
res--;
}
}
}
return res;
}
bool isSimilar(string str1, string str2){
int diff = 0;
for(int i = 0; i < str1.size(); i++){
if(str1[i] != str2[i]){
diff++;
}
}
return diff <= 2;
}
int find(vector<int>& fathers, int x){
if(fathers[x] != x){
fathers[x] = find(fathers, fathers[x]);
}
return fathers[x];
}
bool unionStr(vector<int>& fathers, int x, int y){
int fx = find(fathers, x);
int fy = find(fathers, y);
if(fx != fy){
fathers[fx] = fy;
return true;
}
return false;
}
};
|
- 时间复杂度：$O(n^2 \cdot L)$
- 空间复杂度：O(n)
分析
判断一条边会不会导致环的规律。如果两个节点分别属于两个不同的子图，添加一条边连接这两个节点，会将它们所在的子图连在一起，但不会形成环。如果两个节点属于同一个子图，添加一条边连接这两个节点就会形成一个环。
因此，为了找到多余的边需要解决两个问题：一是如何判断两个节点是否属于同一个子图，二是如何合并两个子图。并查集刚好可以解决这两个问题，由此可见，这是一个适合用并查集解决的问题。
由于题目指出节点的编号从1到n，逐一扫描边的数组edges得到最大的节点编号确定n的值。接下来初始化并查集，将n个节点初始化为n个子集，每个节点的根节点都指向它自己，即“fathers[i]=i”。接下来逐一在图中添加边，直到某条边的两个节点属于同一个子集，此时函数union将返回false。添加这条边将导致图中出现环，对于树而言这条边就是多余的。
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
| class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int maxVertex = 0;
for(auto& edge : edges){
maxVertex = max(maxVertex, edge[0]);
maxVertex = max(maxVertex, edge[1]);
}
vector<int> fathers(maxVertex + 1);
for(int i = 1; i <= maxVertex; i++){
fathers[i] = i;
}
for(auto& edge : edges){
if(!unionEdges(fathers, edge[0], edge[1])){
return edge;
}
}
return vector<int>(2);
}
int find(vector<int>& fathers, int x){
if(fathers[x] != x){
fathers[x] = find(fathers, fathers[x]);
}
return fathers[x];
}
bool unionEdges(vector<int>& fathers, int x, int y){
int fx = find(fathers, x);
int fy = find(fathers, y);
if(fx != fy){
fathers[fx] = fy;
return true;
}
return false;
}
};
|
图搜索
如果将每个整数看成图中的一个节点，相邻的（数值大小相差1）两个整数有一条边相连，那么这些整数将形成若干子图，每个连续数值序列对应一个子图。计算最长连续序列的长度就转变成求最大子图的大小。
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
| class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> hashset;
for(int num : nums){
hashset.insert(num);
}
int res = 0;
for(int num : nums){
if(hashset.count(num)){
res = max(res, bfs(hashset, num));
}
}
return res;
}
int bfs(unordered_set<int>& hashset, int num){
queue<int> que;
que.push(num);
int len = 0;
while(!que.empty()){
int cur = que.front();
que.pop();
hashset.erase(cur);
len++;
if(hashset.count(cur + 1)){
que.push(cur + 1);
}
if(hashset.count(cur - 1)){
que.push(cur - 1);
}
}
return len;
}
};
|
- 时间复杂度：假设输入n个整数，两个相邻的整数存在一条边，因此图中有n个节点、O（n）条边。在图中进行广度优先搜索的时间复杂度是O（n）。
- 空间复杂度：hashset和queue存储最多n个数，即O(n)。
并查集
在初始化并查集的时候输入数组中的每个整数放入一个子集中，父节点的指针指向它自己。然后对于每个整数n，如果存在整数n-1和n+1，则将它们所在的子集合并。每个子集的根节点记录它所在子集的元素的数目，在合并子集的时候需要更新合并之后新子集的根节点中子集元素的数目。
用哈希表fathers记录每个整数所在子集的父节点，哈希表counts用来记录以某个整数为根节点的子集中整数的数目。初始化并查集的时候每个整数的父节点都指向自己，也就是每个子集中只包含一个数字，所以哈希表counts的每个整数对应的值都被初始化为1。
接下来对于每个整数num，如果存在num-1和num+1，当它们在不同的子图中时将它们所在的子图用函数union合并，并更新合并后子集中元素的数目。判断两个整数是否在同一个子集中的方法是用函数findFather得到它们所在子集的根节点并判断根节点是否相同。
在将所有可能合并的子集合并之后，扫描哈希表就能得到最大子集的大小，即最长连续数值序列的长度。
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
| class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int, int> fathers;
unordered_map<int, int> counts;
unordered_set<int> hashset;
for(int num : nums){
fathers[num] = num;
counts[num] = 1;
hashset.insert(num);
}
for(int num : nums){
if(hashset.count(num + 1)){
unionNum(fathers, counts, num, num + 1);
}
if(hashset.count(num - 1)){
unionNum(fathers, counts, num, num - 1);
}
}
int res = 0;
for(auto& iter : counts){
res = max(res, iter.second);
}
return res;
}
int find(unordered_map<int, int>& fathers, int x){
if(fathers[x] != x){
fathers[x] = find(fathers, fathers[x]);
}
return fathers[x];
}
void unionNum(unordered_map<int, int>& fathers, unordered_map<int, int>& counts, int x, int y){
int fx = find(fathers, x);
int fy = find(fathers, y);
if(fx != fy){
fathers[fx] = fy;
counts[fy] += counts[fx];
}
}
};
|
- 时间复杂度：上述代码可能需要合并相邻的整数O（n）次。由于函数findFather在查找根节点的同时进行了路径压缩，查找操作的平均时间复杂度可以近似看成O（1）。因此，这种基于并查集的解法的时间复杂度是O（n）。
- 空间复杂度：fathers,counts,hashset都是O(n)。
总结
图在算法面试中经常出现，它的背景可能会千变万化，有可能是关于一个矩阵，也可能是关于某些物体或人物，但万变不离其宗，只要深刻理解图是用来研究物体与物体之间的关系的。物体就是图中的节点，如果两个物体之间存在某种关系，那么这两个物体在图中对应的节点之间就有一条边相连。很多时候找到图中的节点和边是解决图的问题的关键。
图的搜索算法是关于图的最重要的算法。很多图的问题都可以用广度优先搜索或深度优先搜索解决。但如果要求无权图中最短路径的长度，那么广度优先搜索是更好的选择；如果路径及路径上节点的顺序对于解决某个图的问题非常关键，那么可以考虑使用深度优先搜索。
拓扑排序可以解决与任务顺序相关的问题。如果某些任务必须在其他任务之前（或之后）完成，则可以用一个有向图描述任务之间的依赖关系，然后通过拓扑排序得到所有任务的执行顺序。
如果一个问题对应的图可以分成若干子图，并且需要判断两个节点是否在同一个子图中且在某些时候合并两个子图，那么可以考虑采用并查集来解决这个问题。并查集用一个树形结构表示集合中的一个子集，每个子集对应图中的一个子图。
刷题心得
至此，《剑指offer专项突破版》的119道题目都刷了一遍，能够感受到在同一种问题下，知道前面的题怎么做了之后，后面的题会做得更轻松。但是还是有点一边做一边忘了，需要再进行复习，复习的时候需要再进行一些拓展。
严格来说是从3月1日开始刷的，中间也因为期末考试等等原因暂停过一段时间，将近五个月的时间，可以说是非常慢了。这学期的行动力非常差，经常陷入到无休止地内耗中，一边焦虑一边无所事事。但还好，起码在这件事上坚持了下来，虽然很慢，但好歹是做了东西的。不敢想象如果连这件事都没坚持下来，这个学期会是多么失败。
之后的计划是按照leetcode算法笔记来继续刷，从04. 基础算法篇开始，到08. 各章节习题解析结束，大概需要两个月的时间。以后一定要提高学习效率，不能一心多用，想一些和自己无关的事，把时间白白浪费掉。
研一基本上算是结束了，如果说自己什么都没干，一点收获都没有的话，好像也太苛责自己了，毕竟还有那么多焦虑的时间，也不能全怪自己。悟已往之不谏，既然过去了，那就让它过去吧。
种一棵树最好的时间是十年前，其次是现在。