专栏首页算法修养LeetCode 200. Number of Islands(并查集)

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 3450 Counting Sequences(线段树)

    Counting Sequences Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 3276...

    ShenduCC
  • PTA 甲级 1139

    https://pintia.cn/problem-sets/994805342720868352/problems/994805344776077312

    ShenduCC
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • 挑战程序竞赛系列(27):3.5二分图匹配(2)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 挑战程序竞赛系列(35):3.3Binary Indexed Tree

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • BZOJ1046: [HAOI2007]上升序列(LIS)

      对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1 < x2 < … < xm)且( ax1 < ...

    attack
  • Sicily 8843 Ranking and Friendship

    http://soj.me/8843 题意:几个人想做好朋友,朋友之间相差位置小于等于k,且长度相同 分析;排序,将长度相同的放在一起。若长度相同,第i个人能放...

    用户1624346
  • POJ 刷题系列:1083. Moving Tables

    POJ 刷题系列:1083. Moving Tables 传送门:POJ 1083. Moving Tables 题意: 一条走廊,两栏房间。搬运工每次从房价...

    用户1147447
  • Android进阶教程之ViewGroup自定义布局

    在我们的实际应用中, 经常需要用到自定义控件,比如自定义圆形头像,自定义计步器等等。但有时我们不仅需要自定义控件,举个例子,FloatingActionButt...

    砸漏
  • 问题 1426: [蓝桥杯][历届试题]九宫重排

    总的来说题意就是看两个字符串经过最少多少步能成为相同的,我是用广搜做的,有上下左右四个方向,把把两个位置的数字和’.'调换,看和想要的字符串是否相同,用map记...

    用户7727433

扫码关注云+社区

领取腾讯云代金券