点击阅读更多查看文章内容
算法笔记——并查集
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。
关于并查集的讲解有很多大佬的博客都写的很好，这里我主要是参考这篇文章——并查集
定义
并查集实际上是一种树形结构，可以用来查询连通分支的个数，属于同一连通分支的在同一棵树上
主要变量
pre[]:记录结点的前驱结点
rank[]:记录结点的高度
count:记录连通分支的个数
主要函数
init():初始化
join(x,y):合并x,y结点
find(x):查找x结点所在树的根节点
函数定义
1.find()
这里通过find要一直找到根节点，当pre[x]=x时即找到根节点
如果不等就一直往上查找即可，这里在返回时对pre[x]进行修改，可以压缩查找路径，具体原理在文章开头的博客中都有讲到
1
2
3
4
5
6
7
| int find(int x)
{
if (pre[x] == x)
return x;
else
return pre[x] = find(pre[x]);
}
|
2.join()
要想连接两个结点，只需要把其中一个结点所在树的根节点接到另一棵树的根节点即可
- 首先判断两个结点是否属于同一棵树，即判断两个结点的根节点是否相等即可，如果相等，则两个结点已经连通，直接返回。
- 这里我们希望将高度小的树连接到高度大的树上，这样可以缩小连接后树的高度，所以首先分别对两棵树根节点的高度进行判断，如果高度不相等，则将小的连接到大的上，此时连接后原本的rank不变，如果两棵树高度相等的话，则被连接上的树的高度要加1，这里大家可以自己画图看看，还是比较好理解的。
- 两棵树相连后，总的连通分量的个数要减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
| void join(int x, int y)
{
x = find(x);
y = find(y);
if (x == y)
return;
if (rank[x] < rank[y])
{
pre[x] = y;
}
else
{
if (rank[x] == rank[y])
{
pre[x] = y;
rank[y]++;
}
else
{
pre[y] = x;
}
}
count--;
}
|
3. init()
关于init()函数主要是对pre[]以及rank[]的初始化，大家看文章最后的例题来加深理解。
例题
并查集对不同题目中只有初始化方面有所不同，其它函数基本一致，下面通过两道例题主要感受一下并查集该怎么初始化，代码用到的都是上面刚刚写好的模板
547. 省份数量
代码:
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
| class UnionFind
{
private:
vector<int> pre;
vector<int> rank;
int count = 0;
public:
UnionFind(vector<vector<int>> isConnected)
{
int n = isConnected.size();
for (int i = 0; i < n; i++)
{
pre.push_back(i);
rank.push_back(1);
count++;
}
}
int find(int x)
{
if (x == pre[x])
return x;
else
return pre[x] = find(pre[x]);
}
void join(int x, int y)
{
x = find(x);
y = find(y);
if (x == y)
return;
if (rank[x] < rank[y])
pre[x] = y;
else
{
if (rank[x] == rank[y])
{
pre[x] = y;
rank[y]++;
}
else
pre[y] = x;
}
count--;
return;
}
int getCount()
{
return count;
}
};
class Solution
{
public:
int findCircleNum(vector<vector<int>> &isConnected)
{
UnionFind uf(isConnected);
int n = isConnected.size();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (isConnected[i][j])
uf.join(i, j);
}
}
return uf.getCount();
}
};
|
200. 岛屿数量
代码：
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
95
96
97
98
99
100
101
102
103
104
105
106
| class UnionFind
{
private:
vector<int> pre;
vector<int> rank;
int count = 0;
public:
UnionFind(vector<vector<char>> grid)
{
int n = grid.size();
int m = grid[0].size();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (grid[i][j] == '1')
{
pre.push_back(i * m + j);
rank.push_back(1);
count++;
}
else
{
pre.push_back(-1);
rank.push_back(-1);
}
}
}
}
int find(int x)
{
if (pre[x] == x)
return x;
else
return pre[x] = find(pre[x]);
}
void join(int x, int y)
{
x = find(x);
y = find(y);
if (x == y)
return;
if (rank[x] < rank[y])
{
pre[x] = y;
}
else
{
if (rank[x] == rank[y])
{
pre[x] = y;
rank[y]++;
}
else
{
pre[y] = x;
}
}
count--;
}
int getCount()
{
return count;
}
};
class Solution
{
private:
int fx[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public:
int numIslands(vector<vector<char>> &grid)
{
int n = grid.size();
int m = grid[0].size();
UnionFind uf(grid);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (grid[i][j] == '1')
{
grid[i][j] = '0';
for (int k = 0; k < 4; k++)
{
int newi = i + fx[k][0];
int newj = j + fx[k][1];
if (newi >= 0 && newi < n && newj >= 0 && newj < m && grid[newi][newj] == '1')
{
uf.join(i * m + j, newi * m + newj);
}
}
}
}
}
return uf.getCount();
}
};
|
