跳转至

684 冗余连接

https://leetcode.cn/problems/redundant-connection/

本题给出n个点和n条边,由于树的边数为节点数 -1, 所以实际上只会多出一条边,这条边就是我们要求的解

如果多条答案边,创一个ans数组依次放入,最后返回末尾元素即可(即栈顶元素)

class Solution {
private:
    vector<int> p;
    void init(int n){
        p.resize(n + 1);
        for(int i = 1; i <= n; i++)
            p[i] = i;
    }
    int Find(int x){
        if(p[x] != x) p[x] = Find(p[x]);
        return p[x];
    }
    void Union(int x, int y){
        p[Find(x)] = Find(y);
    }
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        init(n);
        for(auto edge: edges){
            int x = edge[0], y = edge[1];
            if(Find(x) != Find(y)){
                Union(x, y);
            }
            // p[x] == p[y]说明x和y在一棵树中了,此时多加的那条边会使树变成图,即题解
            else return edge;
        }
        return vector<int>();
    }
};