思考:
1.甚麼是Redundant Connection(多餘的連結)，在一個Graphs中去除這條邊也能形成連通圖
2.利用Union-find
3.分為 Union_set 和 find_set

Union_set : 用來檢測這一條邊的兩個點a, b是不是有同一個父點(根節點)，如果是則產生cycle
如果不是則設定b來自於a
find_set : 設定來源的點的父點(根節點)為誰

class Solution {
public:
    vector <int> parent;
    int find_parent(int a){
        if(a == parent[a]){
            //目前父節點就是自己
            return parent[a];
        }else{
            //追朔到最上層的父節點
            parent[a] = find_parent(parent[a]);
            return parent[a];
        }
    }

    bool Union(int a, int b){
        a = find_parent(a);
        b = find_parent(b);
        if(a == b){
            //代表有相同父節點, 這條邊加上去會形成cycle
            return true;
        }else{
            //代表沒有相同父節點, b來源於a
            parent[b] = a;
            return false;
        }
    }






    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        //利用Union set來找到多餘的那條邊
        //主要是每一個節點的父節點
        //如果出現一條邊的a, b點都有相同父節點, 代表加入這條邊就會造成cycle
        int n = edges.size();
        //初始化每個節點的parant都是自己
        //<= 是因為 點從 1 開始
        for(int i = 0; i <= n; i++){
            parent.push_back(i);
        }

        //開始掃描每一條邊
        for(vector<int> edge : edges){
            if(Union(edge[0], edge[1])){
                for(int i : parent){
                    printf("%d", i);
                }                
                return {edge[0], edge[1]};
            }
        }
        return {-1,-1};
    }
};

class Solution {
    vector<int> parent;  // 儲存點的父點

    int find_set(int v) {
        if (v == parent[v])  // 如果點的父點是自己，說明找到這個集合的根結點
            return v;
        return parent[v] = find_set(parent[v]);  // 路徑壓縮，將節點直接連接到"根"節點，提高查找效率
    }

    bool union_set(int a, int b) {
        a = find_set(a);  // 找節點a所屬的集合的根結點
        b = find_set(b);  // 找節點b所屬的集合的根結點
        if (a == b)  // 如果a和b的根結點相同，說明a,b已經在同一個集合中，加入這條邊會造成迴路
            return true;
        parent[b] = a;  // 否則, 將b的父節點連接到a的父節點合併集合
        return false;
    }

public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();

        for (int i = 0; i <= n; i++)
            parent.push_back(i);  // 初始化，每一個節點的父親都預設為自己

        for (vector<int> edge : edges) {
            if (union_set(edge[0], edge[1]))  // 嘗試將兩個節點合併到同一個集合內
                return {edge[0], edge[1]};  // 如果這條節點會形成迴圈則代表是多餘的
        }
        
        return {-1, -1};  // 如果跑完全部的節點都沒找到形成迴路的邊，代表無
    }
};
//預設每一個點的父節點都是自己
//1 2 3
//1 2 3
//
//[1,2] ->檢查 1 和 2 的父節點 1是1, 2是2, 則 2的父節點為 1 
//[1,3] ->檢查 1 和 3 的父節點 1是1, 3是3, 則 3的父節點為 1
//[2,3] ->檢查 2 和 3 的父節點 2是1, 3是1, 則true 此邊為reduentent connection