LeetCode 684. 【并查集】冗余链接
原题链接
中等
作者:
大明湖的鱼
,
2021-01-30 01:04:50
,
所有人可见
,
阅读 373
疑问:怎么保证返回的是数组中最后出现的边呢?
class Solution {
public:
int find(vector<int>& parent,int index){
if(parent[index]!=index){
parent[index] = find(parent,parent[index]);
}
return parent[index];
}
void merge(vector<int>& parent,int u,int v){
parent[find(parent,u)] = find(parent,v);
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int nodeCount = edges.size();
vector<int> parent(nodeCount+1);
for(int i = 1;i<nodeCount;i++){
parent[i] = i;
}
for(auto it : edges){
int node1 = it[0],node2 = it[1];
if(find(parent,node1)!=find(parent,node2))merge(parent,node1,node2);
else return it;
}
return vector<int>{};
}
};