Re: [閒聊] 每日leetcode

[dont (dont)]

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
噓 Sougou: -2才有时间刷LC