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
| class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
const int n = edges.size();
vector<int> f(n + 1, 0);
vector<int> size(n + 1, 0);
auto find = [&](int i) {
int j = i;
while (i != f[i]) i = f[i];
while (j != i) {
int next = f[j];
f[j] = i;
j = next;
}
return j;
};
for (const auto& edge : edges) {
int u = edge[0], v = edge[1];
if (!f[u]) f[u] = u;
if (!f[v]) f[v] = v;
int uf = find(u), vf = find(v);
if (uf == vf) return edge;
if (size[vf] > size[uf])
swap(vf, uf);
f[vf] = uf;
size[uf] += size[vf];
}
return {};
}
};
|