leetcode/algorithms/cpp/redundantConnection/redundantConnection.cpp at main · MichelleZ/leetcode · GitHub

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
// Source: https://leetcode.com/problems/redundant-connection/
// Author: Miao Zhang
// Date:   2021-03-01

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> parents(edges.size() + 1, 0);
        vector<int> sizes(edges.size() + 1, 1);
        for (const auto& edge: edges) {
            int u = edge[0];
            int v = edge[1];
            if (!parents[u]) parents[u] = u;
            if (!parents[v]) parents[v] = v;
            int pu = find(u, parents);
            int pv = find(v, parents);
            if (pu == pv) return edge;
            if (sizes[pv] > sizes[pu]) {
                swap(pv, pu);
            }
            parents[pv] = pu;
            sizes[pu] += sizes[pv];
        }
        return {};
    }

private:
    int find(int node, vector<int>& parents) {
        while (parents[node] != node) {
            parents[node] = parents[parents[node]];
            node = parents[node];
        }
        return node;
    }
};