并查集是一种可以动态维护若干个不重叠的结合,并且支持合并与查询的数据结构.也就是擅长维护各种各样的具有传递性质的关系.
基本操作：
- Find 操作，查询一个元素所属哪一个集合。
- Union 合并操作，把两个集合合并成一个集合。
并查集算法模板
c++版本代码
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
| class UnionFind{
public:
vector<int>father;
UnionFind(int num){//num表示元素的个数
// 使用树形结构存储每个集合,刚开始的时候每个点就是一个独立的集合,且这个集合树的树根就是本身.
for(int i = 0; i < num; i++){
father.push_back(i);//箭头指向自己
}
}
int Find(int n){
//递归
if(father[n] == n)
return n;
return Find(father[n]); // 正常版本
}
/**
* 按秩合并:秩有两种定义,一个是未压缩过的树的深度,一个是集合的大小,但是lyd大佬说,无论采用任何一种定义,我们统统可以把集合的秩记录在树根上,然后每一个合并都让秩较小的数,做秩较大的树根子节点.
*/
void Union(int a, int b){
int fa = Find(a);
int fb = Find(b)
father[fb] = fa;
}
};
/**
* 优化版本
*/
class UnionFind{
public:
vector<int>father;
vector<int> size;
UnionFind(int num){//num表示元素的个数
// 使用树形结构存储每个集合,刚开始的时候每个点就是一个独立的集合,且这个集合树的树根就是本身.
for(int i = 0; i < num; i++){
father.push_back(i);//箭头指向自己
}
size = vector<int>(num); // 按秩合并
}
int Find(int n){
//递归
if(father[n] == n)
return n;
// 路径压缩:每一个执行Find操作的时候,把访问过的节点(也就是所有元素的父亲),都统统指向树根祖宗.
father[n] = Find(father[n]);//路径压缩版本
return father[n];
}
/**
* 按秩合并:秩有两种定义,一个是未压缩过的树的深度,一个是集合的大小,但是lyd大佬说,无论采用任何一种定义,我们统统可以把集合的秩记录在树根上,然后每一个合并都让秩较小的数,做秩较大的树根子节点.
*/
void Union(int a, int b){
int fa = Find(a);
int fb = Find(b);
// 按秩合并
// if (fa == fb) return; // 这句按照需求可添可删
if (size[fb] < size[fa]) {
father[fb] = fa;
size[fa]++;
} else {
father[fa] = fb;
size[fb]++;
}
}
};
|
常见操作
统计连通块的数量
1
2
3
4
| unordered_set<int> hash;
// 统计连通块的数量
for (int i = 0; i < n; i++) hash.insert(find(i)); // 查找
hash.size();// 即为连通块的数量
|
统计环的数量
1
2
3
4
5
| int cnt = 0; // 记录环的数量
for (int i = 0; i < n; i++) {
int root = find(i);
if (root == i) cnt++; // 统计环
}
|
统计连通块中结点的数量
1
2
3
4
5
6
7
8
9
10
11
| unordered_map<int, int> cnt; // 键为每个联通块中的父节点，值为当前连通块中的节点数
for (auto a : A) cnt[find(a)]++;
// 或者
vector<int> cnt(n); //同理，索引就是父节点，父节点所在连通区域的节点数量
for (int i = 0; i < n; i++) cnt[find(i)]++;
// 找最大的连通区域，直接遍历哈希表或者数组找最大值即可，如：
vector<int> cnt(n);
int res = 0;
for (int i = 0; i < n; i++) res = max(res, ++cnt[find(i)]); // 更新res即可，注意这儿是先++
|
- 暂时还没遇到。。。
除数求值(中等)
朋友圈(中等)
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。朋友圈
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| vector<int> p; // 根节点集合
/**
* 并查集
*/
int findCircleNum(vector<vector<int>>& M) {
int n = M.size();
p = vector<int>(n);
for (int i = 0; i < n; i++) p[i] = i; // 初始化，自己指向自己
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (M[i][j]) p[find(i)] = find(j); // 合并
unordered_set<int> hash;
// 统计连通块的数量
for (int i = 0; i < n; i++) hash.insert(find(i)); // 查找
return hash.size();
}
// 查找
int find(int n) {
if (n == p[n]) return n;
p[n] = find(p[n]);
return p[n];
}
|
冗余连接(中等)
在本问题中, 树指的是一个连通且无环的无向图。输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < 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
| vector<int> p; // 根节点集合
/**
* 并查集
*/
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
p = vector<int>(n + 1);
for (int i = 1; i <= n; i++) p[i] = i; // 初始化，自己指向自己
for (auto e : edges) {
// 查找，如果一条边的两个端点在一个集合中，说明构成回路了，直接返回
if (find(e[0]) == find(e[1])) return {e[0], e[1]};
p[find(e[0])] = find(e[1]); // 合并
}
return {-1, -1};
}
/**
* 查找函数
*/
int find(int x) {
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
|
冗余连接II(中等)
在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。结果图是一个以边组成的二维数组。 每一个边 的元素是一对 [u, v]，用以表示有向图中连接顶点 u 和顶点 v 的边，其中 u 是 v 的一个父节点。返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。冗余连接II
参考代码
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
| vector<int> p; // 根节点集合
/**
* 并查集
* 分三种情况，无环但有一个结点的入度为2，有环且环中节点的入度为2，有环但入度都为1
*/
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int n = edges.size();
p = vector<int>(n + 1);
for (int i = 1; i <= n; i++) p[i] = i; // 初始化，自己指向自己
vector<int> d(n + 1); // 统计入度
vector<int> res1, res2; // 记录前一个和后一个的边
for (auto& e : edges) {
int u = e[0], v = e[1];
if (d[e[1]] > 0) {
res1 = {d[v], v};
res2 = e;
e[0] = e[1] = -1;
}
d[v] = u;
}
for (auto e : edges) {
if (e[0] < 0 || e[1] < 0) continue; // 跳过后一个的边
// 查找
if (find(e[0]) == find(e[1])) return res1.empty() ? e : res1;
p[find(e[0])] = find(e[1]); //合并
}
return res2;
}
int find(int x) {
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
|
账户合并(中等)
给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该帐户的邮箱地址。现在，我们想合并这些帐户。如果两个帐户都有一些共同的邮件地址，则两个帐户必定属于同一个人。请注意，即使两个帐户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户，但其所有帐户都具有相同的名称。合并帐户后，按以下格式返回帐户：每个帐户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。accounts 本身可以以任意顺序返回。账户合并
参考代码
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
| vector<int> p; // 根节点集合
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
int n = accounts.size();
p = vector<int>(n);
for (int i = 0; i < n; i++) p[i] = i; // 初始化，自己指向自己
unordered_set<string> hash; // 用于判断邮箱是否已经出现
unordered_map<string, int> father; // 用于记录当前邮箱的父辈
// 遍历每个人名下的每个邮箱，遍历结束后会得到更新后的父辈关系
for (int i = 0; i < n; i++) {
for (int j = 1; j < accounts[i].size(); j++) {
// 判断该邮箱是否是第一次出现
if (!hash.count(accounts[i][j])) { // 若是的话，标记父辈
hash.insert(accounts[i][j]);
father[accounts[i][j]] = i;
} else { // 如不是，则合并当前结点和父辈结点
p[find(father[accounts[i][j]])] = find(i);
}
}
}
// 遍历accounts中每个人名，寻找每个人名的父辈，并将该人名下所有邮箱保存到一起
unordered_map<int, set<string>> t;
for (int i = 0; i < n; i++) {
int f = find(i); // 寻找当前用户的父辈
// 将当前人名下的邮箱添加到父辈下
for (int j = 1; j < accounts[i].size(); j++)
t[f].insert(accounts[i][j]);
}
vector<vector<string>> res;
// 构造答案数组
for (auto a : t) {
vector<string> ans;
ans.push_back(accounts[a.first][0]);
for (auto m : a.second) ans.push_back(m);
res.push_back(ans);
}
return res;
}
int find(int x) {
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
|
情侣牵手(困难)
N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。情侣牵手
思路：我们设想一下加入有两对情侣互相坐错了位置，我们至多只需要换一次。如果三对情侣相互坐错了位置，A1+B2,B1+C2,C1+A2。他们三个之间形成了一个环，我们只需要交换两次。如果四队情侣相互坐错了位置，即这四对情侣不与其他情侣坐在一起，A1+B2,B1+C2,C1+D2,D1+A2.他们四个之间形成了一个环，他们只需要交换三次并且不用和其他情侣交换，就可以将这四对情侣交换好，以此类推，其实就是假设k对情侣形成一个环状的错误链，我们只需要交换k - 1次就可以将这k对情侣的位置排好。所以问题转化成N对情侣中，有几个这样的错误环。我们可以使用并查集来处理，每次遍历相邻的两个位置，如果他们本来就是情侣，他们处于大小为1的错误环中，只需要交换0次。如果不是情侣，说明他们呢两对处在同一个错误环中，我们将他们合并（union），将所有的错坐情侣合并和后，答案就是情侣对 - 环个数。这也说明，最差的情况就是所有N对情侣都在一个环中，这时候我们需要N - 1调换。最好情况每对情侣已经坐好了，已经有N个大小为1的环，这时候我们需要N - N次调换。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| vector<int> p; // 根节点集合
int minSwapsCouples(vector<int>& row) {
int m = row.size();
p = vector<int>(m / 2);
for (int i = 0; i < m / 2; i++) p[i] = i; // 初始化
int res = 0;
for (int i = 0; i < m; i += 2) // 将情侣合并
p[find(row[i] / 2)] = find(row[i + 1] / 2);
for (int i = 0; i < m / 2; i++) // 判断里面有多少个环
// 判断是否为环
if (find(i) == i) res++;
return m / 2 - res;
}
int find(int x) {
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
|
相似字符串组(困难)
如果我们交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。我们给出了一个不包含重复的字符串列表 A。列表中的每个字符串都是 A 中其它所有字符串的一个字母异位词。请问 A 中有多少个相似字符串组？相似字符串组
参考代码
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
| vector<int> p; // 根节点集合
int numSimilarGroups(vector<string>& A) {
int n = A.size();
p = vector<int>(n);
for (int i = 0; i < n; i++) p[i] = i; // 初始化
// 单词两两合并
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (similar(A[i], A[j])) p[find(i)] = find(j);
unordered_set<int> hash;
// 统计最后有多少个连通块
for (int i = 0; i < n; i++) hash.insert(find(i));
return hash.size();
}
int find(int x) {
if (x == p[x]) return x;
p[x] = find(p[x]); // 路径压缩优化很关键，不优化会超时
return p[x];
}
bool similar(string& s1, string& s2) {
int cnt = 0;
for (int i = 0; i < s1.size(); i++)
if (s1[i] != s2[i]) cnt++;
return cnt <= 2;
}
|
信息传递(中等)
有 n 个同学（编号为 1 到 n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 Ti 的同学。游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？信息传递
参考代码
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
| #include <bits/stdc++.h>
using namespace std;
vector<int> p;
int cnt = 0, res = INT_MAX;
int find(int x) { // 查找，不能使用路径压缩，因为要统计路径上有多少人，只查找的话可以进行路径压缩
cnt++; // 统计最小环的长度
if (x == p[x]) return x;
return find(p[x]);
}
int main() {
int n;
cin >> n;
p = vector<int>(n + 1);
for (int i = 1; i <= n; i++) p[i] = i; // 初始化
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
cnt = 0; // 初始化
if (find(x) == i) // 如果再一次遍历到了自己
res = min(res, cnt); // 更新答案
else
p[i] = x; // 设置自己传递对象
}
cout << res << endl;
return 0;
}
|
尽量减少恶意软件的传播(困难)
在节点网络中，只有当 graph[i][j] = 1 时，每个节点 i 能够直接连接到另一个节点 j。一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。我们可以从初始列表中删除一个节点。如果移除这一节点将最小化 M(initial)， 则返回该节点。如果有多个节点满足条件，就返回索引最小的节点。请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后可能仍然因恶意软件传播而受到感染。尽量减少恶意软件的传播
参考代码
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
| vector<int> p; // 根节点集合
vector<int> s; // 连通区域的结点个数
/**
* 问题可以转换成求最大的且只包含一个感染结点的连通区域，这样删除该感染结点，其余的结点就不会再被感染了
*/
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
p = vector<int>(n);
for (int i = 0; i < n; i++) p[i] = i; // 初始化
s = vector<int>(n);
vector<int> affected(n); // 记录联通区域中感染的结点个数
sort(initial.begin(), initial.end()); // 先排序
// 遍历图中的关系，进行union
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (graph[i][j]) Union(i, j);
// 统计每个连通区域感染的结点数
for (int i : initial) affected[Find(i)]++;
int num = 0,
res = -1; // num记录最大连通区域的节点数，res是对应的结点索引
for (int i : initial) {
int root = Find(i);
// 如果当前连通区域的感染结点是一个的话，说明该连通区域是可能的答案
if (affected[root] == 1) {
// 更新最大连通区域的结点数以及对应的感染结点索引
if (num < s[root]) {
num = s[root];
res = i;
}
}
}
return res == -1 ? initial[0] : res;
}
int Find(int x) {
if (x == p[x]) return x;
p[x] = Find(p[x]);
return p[x];
}
void Union(int x, int y) {
int rx = Find(x);
int ry = Find(y);
if (s[rx] < s[ry]) {
p[rx] = ry;
s[ry]++;
} else {
p[ry] = rx;
s[rx]++;
}
}
|
尽量减少恶意软件的传播II(困难)
参考代码
移除最多的同行或同列石头(简单)
我们将石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。每次 move 操作都会移除一块所在行或者列上有其他石头存在的石头。请你设计一个算法，计算最多能执行多少次 move 操作？移除最多的同行或同列石头
参考代码
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
| vector<int> p; // 根节点集合
/**
* 按照行列合并，合并之后每一个连通区域最后会剩一个石头，所以最终答案是总数减去连通区域个数
*/
int removeStones(vector<vector<int>>& stones) {
int n = stones.size();
p = vector<int>(n);
for (int i = 0; i < n; i++) p[i] = i; // 初始化
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 按照行和列进行合并
if (stones[i][0] == stones[j][0] ||
stones[i][1] == stones[j][1])
p[find(i)] = find(j);
}
}
unordered_set<int> hash;
// 统计连通块的数量
for (int i = 0; i < n; i++) hash.insert(find(i));
return n - hash.size();
}
int find(int x) {
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
|
等式方程的可满足性(中等)
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：”a==b” 或 ”a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。等式方程的可满足性
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| vector<int> p; // 根节点集合
bool equationsPossible(vector<string>& equations) {
p = vector<int>(26); // 26个字母
for (int i = 0; i < 26; i++) p[i] = i; // 初始化
for (auto& s : equations) {
if (s[1] == '=') { // 将相等的进行合并
p[find(s[0] - 'a')] = find(s[3] - 'a');
}
}
for (auto& s : equations) {
if (s[1] == '!') { // 判断不等时，两个变量是否是在不同的连通块中
if (find(s[0] - 'a') == find(s[3] - 'a')) return false;
}
}
return true;
}
int find(int x) {
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
|
按公因数计算最大组件大小(困难)
给定一个由不同正整数的组成的非空数组 A，考虑下面的图：有 A.length 个节点，按从 A[0] 到 A[A.length - 1] 标记；只有当 A[i] 和 A[j] 共用一个大于 1 的公因数时，A[i] 和 A[j] 之间才有一条边。返回图中最大连通组件的大小。按公因数计算最大组件大小
参考代码
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
| vector<int> p; // 根节点集合
int largestComponentSize(vector<int>& A) {
int n = A.size();
p = vector<int>(n);
for (int i = 0; i < n; i++) p[i] = i; // 初始化
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) { // 这儿超时了，需要优化时间复杂度应为O(nsqrt(n))
if (gcd(A[i], A[j]) != 1) p[find(i)] = find(j);
}
}
int res = 0;
vector<int> cnt(n);
for (int i = 0; i < n; i++) res = max(res, ++cnt[find(i)]);
return res;
}
// 求最大公约数
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int find(int x) {
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
/**
* 优化版本
*/
unordered_map<int, int> p; // 根节点集合
int largestComponentSize(vector<int>& A) {
for (auto a : A)
for (int k = 2; k * k <= a; k++) // 这儿优化了
if (!(a % k)) p[find(k)] = p[find(a / k)] = p[find(a)];
unordered_map<int, int> cnt;
int res = 0;
for (auto a : A) res = max(res, ++cnt[find(a)]);
return res;
}
int find(int x) {
if (!p.count(x)) return p[x] = x;
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
|
交换字符串中的元素(中等)
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。你可以 任意多次交换 在 pairs 中任意一对索引处的字符。返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。交换字符串中的元素
参考代码
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
| vector<int> p; // 根节点集合
/**
* 首先将可以交换的位置合并成不同的集合，然后按照位置取出字母，并对其进行排序
* 将排好序的字母再插回到原来的索引位置即可。
*/
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n = s.size();
p = vector<int>(n);
for (int i = 0; i < n; i++) p[i] = i; // 初始化
for (auto t : pairs) p[find(t[0])] = find(t[1]); // 合并可以交换的位置
vector<vector<char>> tmp(n); // 按索引求出每个集合中的字母
for (int i = 0; i < n; i++) {
int root = find(i);
tmp[root].push_back(s[i]);
}
for (int i = 0; i < n; i++) { // 对取出的字母按照降序排列
sort(tmp[i].begin(), tmp[i].end());
reverse(tmp[i].begin(), tmp[i].end());
}
string res;
// 构建答案
for (int i = 0; i < n; i++) {
int root = find(i); // 首先找当前字符的根
res += tmp[root].back(); // 从当前根的集合中取最小的字母
tmp[root].pop_back(); // 从当前根的集合中删除当前字母
}
return res;
}
int find(int x) {
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
|
连通网络的操作次数(中等)
用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -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
| vector<int> p; // 根节点集合
/**
* 先将所有连接进行合并，然后找总共有多少个环，总共有多少个连通块，
* 每一个环可以拆出来一根线来连接不同的连通块，所以，环的数量加1要大于等于连通块的数量
*/
int makeConnected(int n, vector<vector<int>>& connections) {
int m = connections.size();
if (m < n - 1) return -1; //如果网线的数量少于结点的数量减一，则肯定连不起来，直接返回-1
p = vector<int>(n);
for (int i = 0; i < n; i++) p[i] = i; // 初始化
for (auto ct : connections) p[find(ct[0])] = find(ct[1]); // 合并
unordered_set<int> hash; // 统计连通块
int cnt = 0; // 记录环的数量
for (int i = 0; i < n; i++) {
int root = find(i);
hash.insert(root); // 入哈希表
if (root == i) cnt++; // 统计环
}
return cnt + 1 >= hash.size() ? hash.size() - 1 : -1;
}
int find(int x) {
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
|
婴儿名字(中等)
每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。在结果列表中，选择字典序最小的名字作为真实名字。婴儿名字
参考代码
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
| vector<int> p; // 根节点集合
typedef pair<string, int> PII;
/**
* 考虑优化一下
*/
vector<string> trulyMostPopular(vector<string>& names,
vector<string>& synonyms) {
int n = names.size();
p = vector<int>(n);
for (int i = 0; i < n; i++) p[i] = i; // 初始化
vector<PII> nms(n); // 用于存储名字和次数
unordered_map<string, int> hash; // 名字和索引对应
for (int i = 0; i < n; i++) {
int pos = names[i].find('(');
nms[i] = {
names[i].substr(0, pos),
stoi(names[i].substr(pos + 1, names[i].size() - pos - 2))};
hash[names[i].substr(0, pos)] = i;
}
for (auto item : synonyms) {
int pos = item.find(',');
string n1 = item.substr(1, pos - 1);
string n2 = item.substr(pos + 1, item.size() - pos - 2);
p[find(hash[n1])] = find(hash[n2]); // 合并
}
vector<string> res;
map<string, int> cnt; // 用于统计合并后名字出现的次数
map<string, vector<string>> tmp; // 用于记录名字集合
for (int i = 0; i < n; i++) {
int root = find(i);
tmp[nms[root].first].push_back(nms[i].first); // 把具有相同根节点的名字保存，以便后续获得这些名字中字典序最小的一个输出
cnt[nms[root].first] += nms[i].second; // 计数
}
for (auto item : cnt) {
sort(tmp[item.first].begin(), tmp[item.first].end()); // 对当前名字集合进行排序
res.push_back(tmp[item.first][0] + "(" + to_string(item.second) + ")");
}
return res;
}
int find(int x) {
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
|
可能的二分法(中等)
给定一组 N 人（编号为 1, 2, …, N）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。当可以用这种方法将每个人分进两组时，返回 true；否则返回 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
| vector<int> p; // 根节点集合
/**
* 运用种类并查集的思想，开两倍的数组，前半部分存放可以分在一组的人，后半部分存放自己不喜欢的人。
*/
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
p = vector<int>(N * 2 + 5); // 并查集
for (int i = 1; i < N * 2 + 5; i++) p[i] = i; // 初始化
for (auto item : dislikes) {
int x = find(item[0]); // 查找自己的根节点
int y = find(item[1]);
int a = find(item[0] + N); // 查找自己不喜欢人的根节点
int b = find(item[1] + N);
if (x == y) // 如果这两个人已经在一组了，不可以！！！返回false
return false;
else { // 否则，将不喜欢的人合并
p[a] = y;
p[b] = x;
}
}
return true;
}
int find(int x) {
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
|
