-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution1202.cpp
More file actions
80 lines (77 loc) · 1.76 KB
/
Solution1202.cpp
File metadata and controls
80 lines (77 loc) · 1.76 KB
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
//
// Solution1202.cpp
// Algorithm
//
// Created by Pancf on 2020/8/4.
// Copyright © 2020 Pancf. All rights reserved.
//
#include "Solution1202.hpp"
class UF
{
private:
vector<int> sz;
vector<int> cnts;
public:
UF(int length)
{
sz = vector<int>();
cnts = vector<int>(length, 1);
for (int i = 0; i < length; ++i) {
sz.push_back(i);
}
}
bool isConnected(int lhs, int rhs)
{
return find(lhs) == find(rhs);
}
int find(int i)
{
while (sz[i] != i) {
i = sz[i];
}
return i;
}
void Union(int lhs, int rhs)
{
if (isConnected(lhs, rhs)) {
return;
}
int lhs_parent = find(lhs);
int rhs_parent = find(rhs);
if (cnts[lhs_parent] < cnts[rhs_parent]) {
sz[lhs_parent] = rhs_parent;
cnts[rhs_parent] += cnts[lhs_parent];
} else {
sz[rhs_parent] = lhs_parent;
cnts[lhs_parent] += cnts[rhs_parent];
}
}
};
string Solution1202::smallestStringWithSwaps(string s, vector<vector<int>>& pairs)
{
if (s.length() == 1) {
return s;
}
// 构造连通图
UF uf((int)s.length());
for (auto pair : pairs) {
uf.Union(pair[0], pair[1]);
}
// 将每个连通图的结点构成一个集合
vector<vector<int>> m(s.length());
for (int i = 0; i < s.length(); ++i) {
m[uf.find(i)].push_back(i);
}
for (auto &ids : m) {
string ss = "";
for (auto id : ids) {
ss += s[id];
}
// 连通区域排序
sort(begin(ss), end(ss));
// 排序后放回原位
for (auto i = 0; i < ids.size(); ++i)
s[ids[i]] = ss[i];
}
return s;
}