684. 冗余连接

发表于 分类于 ， 阅读次数： 本文字数： 123 阅读时长 ≈ 1 分钟

#思路

有环无向图中找出环上最后出现的边

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
class Solution {
public:

    vector<int> parents;

    int dj_root(int a){
        return a==parents[a]? a: parents[a]=dj_root(parents[a]);
    }

    void dj_union(int a, int b){
        a=dj_root(a);
        b=dj_root(b);
        if (a!=b) parents[a]=b;
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = 0;
        for (auto& edge: edges) {
            if (edge[0] > n) n = edge[0];
            if (edge[1] > n) n = edge[1];
        }
        parents.resize(n);
        for (int i=0; i<n; i++){
            parents[i] = i;
        }
        
        for (auto& edge: edges) {
            int a = edge[0]-1;
            int b = edge[1]-1;
            if (dj_root(a) == dj_root(b)) {
                return edge;
            }
            dj_union(a, b);
        }
        return edges.back();
    }
};