今天也是寫union find 的題目，好累～～

解題

• 題目要我們找到一個圖形裡面由許多線串連，哪一條線是多餘的（只有一條，有兩項輸出最後進來的），簡單來說就是去掉哪一條線圖形依舊能串連

利用union find去找父節點，如果有一條線的兩點都指向同一個父節點，就能判是多餘的線了

1. 建立union find function (Find_ 與 merge)
2. 依序填入與搜尋父節點
3. 回傳最後一個傳入的重複線段

然後就runtime error 了

（因為沒有看到他是從 1 開始

code

code 連結

//Redundant Connection
//mid
class Solution {

    int Find_(vector<int> &f,int x){
        if(f[x] != x){
            f[x] = Find_(f,f[x]);
        }
        return f[x];
    }

    void merge(vector<int> &f,vector<int> &rank,int x,int y){
        x = Find_(f,x);
        y = Find_(f,y);

        if(x==y)return;

        if(x < y){
            swap(x,y);
        }
        f[y] = x;
        rank[x] += rank[y];
    }

public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    
        int n = edges.size();
        vector<int> f(n+1),rank(n+1);

        for(int i = 0;i <= n;i++){
            f[i] = i;
            rank[i] = 1;
        }

        map<int,int> have;
        vector<vector<int>> ans;
    
        for(int i = 0;i<n;i++){
            int a = edges[i][0],b = edges[i][1];
            
            if(!have.count(a) && !have.count(b)){
                have[a] = a;
                have[b] = b;
                f[a] = a;
                f[b] = a;
            }
            else if(!have.count(a) && have.count(b)){
                have[a] = b;
                f[a] = b;
            }
            else if(have.count(a) && !have.count(b)){
                have[b] = b;
                f[b] = a;
            }
            else{
                int c1 = Find_(f,a);
                int c2 = Find_(f,b);
                if(c1 == c2){
                    ans.push_back({a,b});
                }
                else{
                    merge(f,rank,a,b);
                }
            }
        }
        return ans.back();
    }
};