题解 | 岛屿数量

#include <unordered_map>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */

    int findRoot(unordered_map<int, int>& parent,int idx)
    {
        if(parent[idx]==-1)return idx;
        return findRoot(parent,parent[idx]);
    }
    void merge(int i,int j,unordered_map<int, int>& parent,vector<vector<char> >& grid,int col_num)
    {
        // for(auto kv:parent)
        // {
        //     cout<<kv.first<<" "<<kv.second<<endl;
        // }
        int current_idx=i*col_num+j;
        if(grid[i][j]=='1')
        {
            parent[i*col_num+j]=-1;
            if(i-1>=0&&grid[i-1][j]=='1')
            {
                int root_idx=findRoot(parent,(i-1)*col_num+j);
                if(root_idx!=current_idx)
                parent[root_idx]=i*col_num+j;
            }
            if(j-1>=0&&grid[i][j-1]=='1')
            {
                int root_idx=findRoot(parent,i*col_num+j-1);
                if(root_idx!=current_idx)
                parent[root_idx]=i*col_num+j;
            }
        }
    }
    int solve(vector<vector<char> >& grid) {
        // write code here
        int row_num=grid.size();
        int col_num=grid[0].size();
        unordered_map<int, int> parent;
        for(int i=0;i<grid.size();++i)
        {
            for(int j=0;j<grid[0].size();++j)
            {
                merge(i,j,parent,grid,col_num);
            }
        }
        int count=0;
        for(auto kv:parent)
        {
            cout<<kv.first<<"'s parent "<<kv.second<<endl;
            if(kv.second==-1)
            count+=1;
        }
        return count;
    }
};

并查集将左上两个节点的集合加入到当前节点的集合，然后统计根节点数目