加码一题
684 Redundant Connect
题目:
给你n个节点
还有n条边 用vector装起来的
他们之中会出现一个循环
请把最早出现 会造成循环的边删掉
思路:
如果要看会不会造成循环
就要想什么时候会有循环
就是一条线从自己连到自己
所以就会变成很多边在看谁会先把自己连起来
所以这个很多坨的就可以用unionfind 做了
每次都看看是不是同一坨
不是同一坨就把彼此连起来
是同一坨 那就有循环
回传
我好想打手枪
```cpp
class UnionFind {
public:
vector<int> onion;
int on;
UnionFind(int n)
{
onion.resize(n);
int on = n;
for(int i = 0 ; i < n ; i ++)onion[i] = i;
}
int find(int x) {
if (onion[x] == x) return x;
return onion[x] = find(onion[x]);
}
void un(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return ;
if(x < y)
{
onion[y] = x;
}
else
{
onion[x] = y;
}
return ;
}
};
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges)
{
int n = edges.size();
vector<int> paper(n+1);
UnionFind *uf = new UnionFind(n);
for(vector<int> e : edges)
{
int a = e[0]-1;
int b = e[1]-1;
if(uf->find(a) == uf->find(b))return e;
uf->un(a,b);
}
return {};
}
};
```