c++ Union-Find


  • 0
    H
    class Solution {
    public:
        int father[2020];
        int Find_set(int x)
       {
        if(x != father[x])
            father[x] = Find_set(father[x]);
        return father[x];
       }
        bool Union(int x, int y)
       {
        int GrandX = Find_set(x);
        int GrandY = Find_set(y);
        if(GrandX == GrandY)
            return false;
            father[GrandY]=GrandX;
            return true;
        
       }
        vector<int> findRedundantConnection(vector<vector<int>>& edges) {
             for(int i=1;i<=2000;i++){
                 father[i] = i;
             }
             int n = edges.size();
             for(int i=0;i<n;i++){
                 int x=edges[i][0],y=edges[i][1];
                 if(!Union(x,y))return (vector<int>){x,y};
             }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.