原题链接

并查集模板。

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:
    int Find(vector<int>& parent, int index) {
        if(parent[index]!=index) {
            return Find(parent, parent[index]);
        }
        return parent[index];
    }
    void Union(vector<int>& parent, int index1, int index2) {
        parent[Find(parent, index1)] = Find(parent, index2);
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> parent(n+1);
        for(int i=0;i<=n;i++) {
            parent[i] = i;
        }
        for(auto& edge: edges) {
            int n1 = edge[0], n2 = edge[1];
            if(Find(parent, n1) != Find(parent, n2)) {
                Union(parent, n1, n2);
            }
            else {
                return edge;
            }
        }
        return {};
    }
};