blob: c5213092b2e7520a73f203f6ba809f24f700ecc5 (
plain)
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
|
#include "leetcode.h"
class Solution {
public:
vector<int> parent;
string smallestStringWithSwaps(string s, vector<vector<int>> &pairs) {
parent.resize(s.length());
map<int, set<int>> obj;
set<int> idx;
string ans = s;
for (int i = 0; i < parent.size(); i++)
parent[i] = i;
for (int i = 0; i < pairs.size(); i++) {
int u = pairs[i][0];
int v = pairs[i][1];
int fx = findParent(u);
int fy = findParent(v);
if (fx != fy)
parent[fy] = fx;
}
for (int i = 0; i < pairs.size(); i++) {
int u = pairs[i][0];
int v = pairs[i][1];
int fx = findParent(u);
obj[fx].insert(u);
obj[fx].insert(v);
}
for (auto it = obj.begin(); it != obj.end(); it++) {
idx = it->second;
vector<pair<char, int>> t;
auto index = idx.begin();
for (index = idx.begin(); index != idx.end(); index++) {
int pos = *index;
char ch = s[pos];
t.push_back({ch, pos});
}
sort(t.begin(), t.end());
index = idx.begin();
for (int i = 0; i < t.size(); i++) {
ans[*index] = t[i].first;
index++;
}
}
return ans;
}
private:
int findParent(int n) {
if (parent[n] == n)
return n;
return parent[n] = findParent(parent[n]);
}
};
int main() {}
|