Returning the right number of islands using Union Find

Question

I am solving a question on LeetCode.com called Number of Islands:

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

I know how to solve it with DFS, but I am learning union-find and came up with the below approach:

class Solution {
public:
    vector<int> parent, sz;
    int counter;

    int find(int i) {
        if(parent[i]==i) return i;
        return parent[i]=find(parent[i]);
    }
    
    void unionf(int one, int two) {
        int p1=find(one);
        int p2=find(two);
        
        if(p1==p2) return;
        if(sz[one]<sz[two]) {
            parent[one]=two;
            sz[two]+=sz[one];
        } else {
            parent[two]=one;
            sz[one]+=sz[two];
        }
        counter--;
    }
    
    int numIslands(vector<vector<char>>& grid) {
        int m=grid.size(), n=grid[0].size();
        parent.resize(m*n);
        iota(begin(parent),end(parent),0);

        sz.resize(m*n,1);
        
        counter=0;
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(grid[i][j]=='0') {
                    continue;
                }
                
                //grid[i][j]=='1'; an island
                counter++;
                int idx=i*n+j;
                //traverse all 4 neighbors
                if(i+1<m && grid[i+1][j]=='1') unionf(idx,(i+1)*n+j);
                if(i-1>=0 && grid[i-1][j]=='1') unionf(idx, (i-1)*n+j);
                if(j+1<n && grid[i][j+1]=='1') unionf(idx, i*n+j+1);
                if(j-1>=0 && grid[i][j-1]=='1') unionf(idx, i*n+j-1);
            }
        }

        return counter;
    }
};

It produces right answers on the sample inputs, but wrong answer for [["1","1","1"],["0","1","0"],["1","1","1"]].

At a high level, my logic is that whenever I encounter an island (1), I increment the counter and call unionf() and try to unify it with its neighbors. If such a unification is possible, I decrement counter in unionf(), since it is linked to its parent island (a connected component) and not a new island.

Could someone please point out what I am missing in my logic? Thanks!

Answer 1

Add some debug print shows some issues in union: Demo.

Changing to:

void unionf(int one, int two) {
    int p1=find(one);
    int p2=find(two);
    
    if (p1 == p2) return;
    if (sz[p1] < sz[p2]) {
        parent[p1] = p2;
        sz[p2] += sz[p1];
    } else {
        parent[p2] = p1;
        sz[p1] += sz[p2];
    }
    std::cout << "union:" << one << " and " << two
              << "(p1: " << p1 << ", p2: " << p2 << ")" << std::endl;
    counter--;
}

fix the issue (not sure about island size though).

Demo