Re: [閒聊] 每日leetcode
684. Redundant Connection
## 思路
UnionFind
照順序把點連起來 如果在同一個GROUP表示有環 -> 回傳該edge
## Code
```cpp
class UnionFind {
public:
UnionFind(int n) {
rank_.resize(n, 1);
root_.resize(n, 0);
for (int i=0; i<n; ++i) {
root_[i] = i;
}
}
int findP(int x) {
if (root_[x] != x) {
root_[x] = findP(root_[x]);
}
return root_[x];
}
bool unionP(int x, int y) {
int rx = findP(x), ry = findP(y);
if (rx == ry) return false;
if (rank_[rx] >= rank_[ry]) {
root_[ry] = rx;
rank_[rx] += rank_[ry];
} else {
root_[rx] = ry;
rank_[ry] += rank_[rx];
}
return true;
}
private:
vector<int> root_;
vector<int> rank_;
};
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
UnionFind uf(n+1);
for (auto edge: edges) {
if (!uf.unionP(edge[0], edge[1])) {
return edge;
}
}
return {};
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 86.48.13.40 (日本)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1738143458.A.961.html
噓
01/29 17:42,
10月前
, 1F
01/29 17:42, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1314 之 1553 篇)：