LeetCode 200. Number of Islands(并查集)

题目

题意：在一个二维矩阵里，找到全是1相连的块，有几个。

题解：使用并查集，将相连的1设为同一个祖先，最后在统计一下就可以了。

class Solution {
public:
    int father[100005];
    int vis[100005];
    int numIslands(vector<vector<char>>& grid) {
        
        int n =grid.size();
        if(n==0)
            return 0;
        int m =grid[0].size();
        
        if(m==0)
            return 0;
        
        for(int i=0;i<n*m;i++)
        {
            father[i]=i;
            vis[i]=0;
        }
        
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                int x = m * i + j;
                
                
                if(grid[i][j]=='1')
                {
                    if(i-1>=0&&grid[i-1][j]=='1')
                    {
                        int f = find(x);
                        int f1 = find((i-1)*m+j);
                        
                        father[f] = f1;
                    }
                    
                    if(j-1>=0&&grid[i][j-1]=='1')
                    {
                        int f = find(x);
                        int f1 = find(i*m+j-1);
                        father[f] = f1;
                    } 
                }
            }
        }
        int ans=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                int x = m * i + j;
                if(grid[i][j]=='1')
                {
                    int f = find(x);
                    if(vis[f]==0)
                    {
                        ans++;
                        vis[f]=1;
                    }
                }
            }
        }
        return ans;
        
    }
    
    int find(int x)
    {
        if(father[x]!=x)
            father[x] = find(father[x]);
        return father[x];
    }
};