C++ Union Find Solution with union by rank and path compression


  • 0
    A

    Union Find is always used for Connected Component Labelling in image process.
    Labelling connected components - Example
    wiki - Disjoint-set data structure
    have fun!

    class Solution
    {
      public:
        int numIslands(const vector<vector<char>> &grid)
        {
            n = grid.size();
            if (n == 0)
                return 0;
            m = grid[0].size();
    
            vector<vector<int>> copyGrid(n + 1, vector<int>(m + 1, 0));
            for (int i = 1; i < n + 1; i++)
                for (int j = 1; j < m + 1; j++)
                    copyGrid[i][j] = grid[i - 1][j - 1] - '0';
    
            onePass(copyGrid);
            parent.resize(numSet + 1, 0);
            nRank.resize(numSet + 1, 0);
    
            makeSet();
            int i = 0;
            while (i < edge.size())
            {
                int u = edge[i++];
                int v = edge[i++];
    
                u = findParent(u);
                v = findParent(v);
                if (u != v)
                {
                    unionSet(u, v);
                    numSet--;
                }
            }
    
            return numSet;
        }
    
      private:
        int n;
        int m;
        int numSet; //num of tree node
        vector<int> edge;
        vector<int> parent;
        vector<int> nRank;
        void onePass(vector<vector<int>> &copyGrid)
        {
            numSet = 0;
            for (int i = 1; i < n + 1; i++)
                for (int j = 1; j < m + 1; j++)
                {
                    if (copyGrid[i][j] != 0)
                    {
                        if (copyGrid[i][j - 1] != 0 || copyGrid[i - 1][j] != 0)
                        {
                            if (copyGrid[i][j - 1] != 0 && copyGrid[i - 1][j] != 0)
                            {
                                copyGrid[i][j] = min(copyGrid[i][j - 1], copyGrid[i - 1][j]);
                                if (copyGrid[i][j - 1] != copyGrid[i - 1][j])  //find edge
                                {
                                    edge.push_back(copyGrid[i - 1][j]);
                                    edge.push_back(copyGrid[i][j - 1]);
                                }
                            }
                            else
                                copyGrid[i][j] = copyGrid[i - 1][j] == 0 ? copyGrid[i][j - 1] : copyGrid[i - 1][j];
                        }
                        else
                            copyGrid[i][j] = ++numSet;
                    }
                }
        }
    
        void makeSet()
        {
            for (int i = 1; i < numSet + 1; i++)
                parent[i] = i;
        }
    
        int findParent(int n) //path compression
        {
            if (parent[n] != n)
                parent[n] = findParent(parent[n]);
            return parent[n];
        }
    
        void unionSet(int parentX, int parentY) //union by rank
        {
            if (nRank[parentX] < nRank[parentY])
                parent[parentX] = parentY;
            else
            {
                parent[parentY] = parentX;
                if (nRank[parentX] == nRank[parentY])
                    nRank[parentX]++;
            }
        }
    };
    

Log in to reply
 

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