# Leetcode 684. Redundant Connection
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/redundant-connection/ 。

想法 :

Disjoint set(DSU)裸題。
用BFS或是DFS應該也能過。

時間複雜度 : O(n)。

程式碼 :

class Solution {
public:
    vector<int> parent, rank;
    
    int Find(int x){
        if(x == parent[x]) return x;
        return parent[x] = Find(parent[x]);
    }
    
    void Union(int x, int y){
        x=Find(x); y=Find(y);
        
        if(rank[y] < rank[x]) parent[y]=x;
        else if(rank[x] < rank[y]) parent[x]=y;
        else{
            parent[x]=y;
            rank[y]++;
        }
        
        return;
    }
    
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int l=edges.size();
        vector<int> ans(2,0);
        
        for(int i=0 ; i<=l ; i++){
            parent.push_back(i);
            rank.push_back(0);
        }
        
        for(int i=0 ; i<l ; i++){
            //cout << Find(edges[i][0]) << " " << Find(edges[i][1]) << endl;
            
            if(Find(edges[i][0]) == Find(edges[i][1])){
                ans[0]=edges[i][0];
                ans[1]=edges[i][1];
                break;
            }
            else{
                Union(edges[i][0], edges[i][1]);
            }
        }
        
        return ans;
    }
};