分析
并查集的应用,把所有二维数组间的关系进行并查集操作,如果两个点已经属于一个集合,那么把它当做答案数组ans。
C++ 代码
class Solution {
public:
int find(int fa[],int x)
{
if(fa[x]!=x) fa[x]=find(fa,fa[x]);
return fa[x];
}
int n;
vector<int> ans;
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n=edges.size();
int fa[n+1];
for(int i=1;i<=n;i++) fa[i]=i;
for(auto pir:edges)
{
int faa=find(fa,pir[0]),fbb=find(fa,pir[1]);
if(faa!=fbb) //二者不在同一个集合,就进行并查集操作
{
fa[faa]=fbb;
}
else ans=pir; //在一个集合,就作为答案
}
return ans;
}
};