思路讲解
无向图判环模版题，做cf之前来练练手
// 如果union函数发现根本不需要合并，那么a本来就在b的这个集合内
// 说明b有两条到达a的通路即形成了环
比较重要的两句话
AC代码
union是保留字，建议改为add（意思反正是这个意思）；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
vector<int> fa(1010);
int n=edges.size();
for(int i=1;i<=n;++i){
fa[i]=i;
}
for(int i=0;i<n;++i){
int a=edges[i][0],b=edges[i][1];
if(!unionn(a,b,fa)){
return {a,b};
}
}
return {0,0};
}
int find(int x , vector<int> &fa){
if(fa[x]!=x)
fa[x]=find(fa[x],fa);
return fa[x];
}
bool unionn(int a, int b, vector<int>& fa){
if(find(a,fa)==find(b,fa)){
return false;
}else{
fa[find(a,fa)]=find(b,fa);
return true;
}
}
};
|
心路历程（WA，TLE，MLE……）
哈哈，第一次写力扣嘛，总归会遇到点问题，比如啥全角字符，什么union保留字，什么·······，不多赘述。