Leetcode-685.冗余链接2
思路
1.首先造成冲突有两种方式分别是成环，两个父亲节点
2.如果一个节点有两个父亲节点，那么多余的边肯定在这个节点的两边中出现
3.还有一种情况就是可能会有即成环又有两个父亲节点，如下
1 2
2 3
3 4
1 4
5 2
如果出现这种情况答案肯定是成环的边是多余的边，否则只会单独成环，或者单独冲突
代码实现
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| class Solution {
int in[10010];
int vis[10010];
int fa[10010];
int pa[10010];
vector<int>g[10010];
vector<int>ans;
bool can[1010][1010];
int find(int x){
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
void unit(int x,int y){
int fx=find(x);
int fy=find(y);
fa[fy]=fx;
}
public:
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
for(int i=1;i<10010;i++)fa[i]=i,pa[i]=i;
int conf = -1, cy = -1;
for(int i=0;i<edges.size();i++){
if(pa[edges[i][1]]!=edges[i][1]){
conf=i;
}else {
pa[edges[i][1]]=edges[i][0];
if(find(edges[i][0])==find(edges[i][1])){
cy = i;
}else{
unit(edges[i][0],edges[i][1]);
}
}
}
if(conf<0){
ans.push_back(edges[cy][0]);
ans.push_back(edges[cy][1]);
}else
{
if(cy>=0)
{
ans.push_back(pa[edges[conf][1]]);
ans.push_back(edges[conf][1]);
}else{
ans.push_back(edges[conf][0]);
ans.push_back(edges[conf][1]);
}
}
return ans;
}
};
|