C++ simple Disjoint-Set implemention


  • 0
    T

    Use usual disjoint-set data structure is enough for this problem.
    Here, store the id in the matrix, and also this id will be the initial set id. Use findSet to get the set id, if the neighbor has a different set id, merge these two sets. Number of id minus number of merge operation is the result for each time.

    For two basic operations of disjoint-set, for findSet, if disjointSets[id]!=id, recursively call findSet(disjointSets[id]). For merge, use the rank(in other words, the depth of the tree) to merge the short tree to the higher tree.

    The code is trucky. Anyone can shorten it?

    class Solution {
    public:
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            vector<int> ret;       
            vector<vector<int>> matrix(m, vector<int>(n,0));
            pair<int,int> arr[4] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
            int idCount = 0;
            this->mergeCount = 0;
            disjointSets.push_back(0);
            ranks.push_back(0);
            for(int i=0, num=positions.size(); i<num; i++){
                int x = positions[i].first;
                int y = positions[i].second;
                if(matrix[x][y]==0){ 
                    idCount++;
                    disjointSets.push_back(idCount);
                    ranks.push_back(0);
                    matrix[x][y] = idCount;
                    for(int j=0; j<4; j++){
                        int x0 = x+arr[j].first;
                        int y0 = y+arr[j].second;
                        // Most important here
                        if(x0>=0 && x0<m && y0>=0 && y0<n && matrix[x0][y0]!=0){
                            if(findSet(idCount)!=findSet(matrix[x0][y0]))
                                merge(idCount, matrix[x0][y0]);
                        }
                    }
                }
                ret.push_back(idCount-this->mergeCount);
            }
            return ret;
        }
        int findSet(int id){
            return (disjointSets[id]==id) ? id : findSet(disjointSets[id]);
        }
        void merge(int id1, int id2){
            int setId1 = findSet(id1);
            int setId2 = findSet(id2);
            if(setId1 == setId2)  return;
            if(ranks[setId1]==ranks[setId2]){
                disjointSets[setId2] = setId1;
                ranks[setId1]++;
            }
            else if(ranks[setId1]>ranks[setId2])
                disjointSets[setId2] = setId1;
            else
                disjointSets[setId1] = setId2;
            this->mergeCount++;
        }
        int mergeCount;
        vector<int> disjointSets;
        vector<int> ranks;
    };

Log in to reply
 

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