题目来源:108. 冗余连接
C++题解(思路来源代码随想录):并查集。因为原来是树,所以加入边之前肯定不是一个根,如果是一个根,再加一条边,肯定成环。所以只要找到根一致的两个点组成的边即可。
#include <iostream>
#include <vector>
using namespace std;
vector<int> father(1001, 0);
int n;
void init(){
for(int i = 1; i <= n; i++){
father[i] = i;
}
}
int find(int u){
if(u == father[u]) return u;
else {
return find(father[u]);
}
}
bool isSame(int u, int v){
if(find(u) == find(v)) return true;
else return false;
}
void join(int u, int v){
u = find(u);
v = find(v);
father[v] = u;
}
int main(){
cin>>n;
init();
for(int i = 1; i <= n; i++){
int a, b; cin>>a>>b;
if(!isSame(a, b)) {
join(a, b);
}
else {
cout<<a<<" "<<b<<endl;
return 0;
}
}
return 0;
}