并查集题目：冗余连接
问题：
思路：
以[1,2] [3,4] [3,2] [1,4] [1,5]为例
初始状态：
读取[1,2]，将1的parent设为2，读取[3,4]同理
读取[3,2]，3所在的集合代表为4, 2所在的集合代表为2
将4的parent设为2
读取[1,4]，1所在的集合代表为2， 4所在的集合代表也为2， 1和4属于同一集合， 1能通过路径到2， 4也能通过路径到2， 1能通过路径到4， 若再加入1到4的边，则1有两条路径到4，一定会出现环， 该条边即为要删除的边
至于题中要求的，返回最后一条边，其实就是返回添加过后会构成环的那一条边
因为在这条边出现之前，图中没有环，这条边出现，图中出现环。包括这条边在内，构成环的边都是满足破环条件的边，即可以删除的边
然而此条构成环的最后一条边就是最后一条出现在此边集合里的边
代码：
class Solution {
public:
int find( int i,int* set )
{
if( set[i]==i )
return i;
else
return find( set[i],set );
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int* set;
set=(int*)malloc( ( edges.size()+1 )*sizeof(int) );
vector<int> ans;
int i;
for( i=1;i<=edges.size();i++ )
set[i]=i;
for( i=0;i<edges.size();i++ )
{
if( find( edges[i][0],set )==find( edges[i][1],set ) )
{
ans.push_back( edges[i][0] );
ans.push_back( edges[i][1] );
break;
}
else
{
set[ find( edges[i][0],set ) ]=find( edges[i][1],set );
}
}
return ans;
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/153843.html
