加碼一題
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 {};
}
};
```