Simple solution with disjoint set in c++


  • 0
    Q
    class Solution 
    {
        int n, m;
        int getidx(int x, int y)
        {
            return x + y * n;
        }
        int getfather(int *f, int a)
        {
            return a == f[a] ? a : f[a] = getfather(f, f[a]);
        }
    public:
        int numIslands(vector<vector<char>> &grid) 
        {
            if (grid.empty() || grid[0].empty()) return 0;
            n = grid.size(); m = grid[0].size();
            int father[n * m];
            
            for (int i = 0; i < n; ++ i)
                for (int j = 0; j < m; ++ j)
                {
                    int nid(getidx(i, j));
                    if (grid[i][j] == '1')
                    {
                        father[nid] = nid;
                        if (i && grid[i - 1][j] == '1')
                            father[getfather(father, nid)] = getfather(father, getidx(i - 1, j));
                        if (j && grid[i][j - 1] == '1')
                            father[getfather(father, nid)] = getfather(father, getidx(i, j - 1));
                    }
                    else
                        father[nid] = -1;
                }
            int cnt(0);
            for (int i = 0; i < n * m; ++ i)
                if (father[i] != -1 && i == getfather(father, i))
                    cnt ++;
            
            return cnt;
        } 
    };

Log in to reply
 

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