使用 Union Find 返回正确数量的岛屿

Question

我正在 LeetCode.com 上解决一个名为岛屿数量的问题：

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.

我知道如何用 DFS 解决它，但我正在学习 union-find 并想出了以下方法：

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;
    }
};

它对样本输入产生正确答案，但对 [["1","1","1"],["0","1","0"],["1","1","1"]] 给出错误答案。

在高层次上，我的逻辑是每当我遇到一个岛（1），我增加计数器并调用unionf()并尝试与它的邻居统一。如果这样的统一是可能的，我在 unionf() 中递减 counter，因为它链接到它的父岛（一个连接的组件）而不是一个新岛。

有人可以指出我的逻辑中缺少什么吗？谢谢！

Answer 1

添加一些调试打印显示联合中的一些问题：Demo。

更改为：

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--;
}

解决问题（虽然不确定岛的大小）。

Demo

使用 Union Find 返回正确数量的岛屿

Returning the right number of islands using Union Find

c++

algorithm

disjoint-sets

union-find

disjoint-union