disjoint set 我最初是在 Kruskal 演算法學到的，但太久沒碰生疏到寫以下題目根本沒想到。

684. Redundant Connection (medium)

題目說明: 給含 n 個節點的圖，回傳一條可以刪除的邊，剩下的圖是一個包含 n 個節點的樹。

一開始想法
DFS 的 "White-Gray-Black"方法去偵測環，但需要得知順序後回傳給刪除的邊，就放棄這想法。

但突然想法太簡單且蠢的寫出以下寫法:
我用一個 set 存沒那些構成環的節點們，我那時認為一條邊的兩節點都不存在 set 裡，就不構成環，而如果兩節點都在 set 裡就會有環。

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        unordered_set<int> mySet;
        mySet.insert(edges[0][0]);
        for (auto e: edges) {
            if (mySet.count(e[0]) && mySet.count(e[1])) {
                return e;
            }
            else if (mySet.count(e[0])) {
                mySet.insert(e[1]);
            }
            else {
                mySet.insert(e[0]);
            }
        }
        return edges[0];
    }
};

然而，過了 15/39 的測資，
這想法的根本錯誤在於無法正確追蹤節點間的關聯性啊!
反例舉例:
輸入: [[1, 2], [3,4], [1, 4]]

1 -- 2
  \
3 - 4 

1, 4 兩節點早就在 set 裡，但再相接這一條邊也是沒問題的。

以下 改成 disjoint set 的寫法
(小注意，題目內的節點邊號是 1-index，因此我的處理是都改成 0-index)
主要想法: 如果邊的兩節點早就在同一個component，那就此邊就會構成環。

class Solution {
public:
    vector<int> parent;
    int f(int v) {
        if (parent[v] == v) return v;
        return f(parent[v]);
    }

    bool find(int v, int w) {
        return f(v) == f(w);
    }

    void push(int v, int w) {
        int rootV = f(v);
        int rootW = f(w);
        parent[rootV] = rootW;  // 把 v 的根連接到 w 的根
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        parent.resize(edges.size());
        for(int i = 0; i < edges.size(); i++){
            parent[i] = i;
        }
        for (auto &e: edges) {
            if(find(e[0]-1, e[1]-1)) {
                return e;
            }
            push(e[0]-1, e[1]-1);
        }
        return {};
    }
};

後來: chatgpt 告訴我，可以多用一個陣列稱為 rank，紀錄樹高，將較矮的樹連接到較高的樹上可以減少未來查找操作的時間，避免樹變得過於深