C++ UnionFind


  • 0
    S

    Does anybody have a better idea on how to quickly find the maximu value int the stats array?

    class UnionFind {
    private:
        std::vector<int> league;
        std::vector<int> stats;
        int cnt;
        
    public:
        UnionFind(int n) : league(n), stats(n), cnt(n){
            for (int i = 0; i < n; ++i) {
                league[i] = i;
                stats[i] = 1;
            }
        }
        
        void connect(int p, int q) {
            int u = root(p);
            int v = root(q);
            if (u == v) return;
            league[v] = u;
            stats[u] += stats[v];
            cnt--;
        }
        
        bool connected(int p, int q) {
            return root(p) == root(q);    
        }
        
        int maxSize() {
            int result = 0;
            for (auto& c : stats) {
                result = std::max(result, c);
            }   
            return result;
        }
        
        int count() const {
            return cnt;
        }
        
        int root(int i) {
            while (i != league[i]) {
                i = league[i] = league[league[i]];
            }
            return i;
        }
    };
    
    class Solution {
    public:
        int maxAreaOfIsland(vector<vector<int>>& grid) {
            int m = grid.size();
            if (m == 0) return 0;
            int n = grid[0].size();
            
            int tot = m * n;
            UnionFind uf(tot + 1);
            bool Found = false;
            for (auto i = 0; i < m; ++i) {
                for (auto j = 0; j < n; ++j) {
                    int k = i * n + j;
                    if (grid[i][j] == 1) {
                        Found = true;
                        if (i > 0 && grid[i - 1][j] == 1) {
                            uf.connect(k - n, k);
                        }
                        if (j > 0 && grid[i][j-1] == 1) {
                            uf.connect(k - 1, k);
                        }
                    }
                }
            }
            return Found ? uf.maxSize() : 0;        
        }
    };
    

Log in to reply
 

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