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>();
}
};