关于使用并查集实现leetcode200号问题

来源:6-7 Flood Fill 的更多优化

martin123_

2019-09-20

老师您好,关于这个问题,我在您提供的695号问题并查集的实现方法的基础上,对代码进行了一定的修改,想法是这样的:
对于岛屿,就按照一般思路寻找其邻点并将他们union;对于海的部分,就将其与某个固定的索引union(事实上我对union多开了一个空间:RC + 1,这个索引指RC),最后在通过对并查集parent数组的扫描,将其中根不是R*C的元素加入一个集合再返回该元素的大小;不知道这个思路是否正确?以下是我的代码(错误的),如果思路错误能否请老师指点别的思路?

//leetcode 200, 使用并查集

import java.util.TreeSet;

class Solution {
    private class UF{
        private int[] parent;

        public UF(int capacity){
            parent = new int[capacity];
            for(int i = 0; i < capacity; i ++)
                parent[i] = i;
        }
        public int find(int p){
            if(parent[p] != p)
                parent[p] = find(parent[p]);
            return parent[p];
        }
        public boolean isConnected(int s, int t){return find(s) == find(t);}
        public void unionElements(int s, int t){
            int sRoot = find(s);
            int tRoot = find(t);
            if(sRoot == tRoot) return;
            parent[sRoot] = tRoot;
        }
        public int treeNumber(){
            TreeSet<Integer> set = new TreeSet<>();
            for(int i = 0; i < parent.length; i ++){
                int x = find(i);
                if(x != parent.length - 1)
                    set.add(x);
            }
            return set.size();
        }
    }
    private int R, C;
    private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    public int numIslands(char[][] grid) {
        if(grid == null) return 0;
        R = grid.length;
        if(R == 0) return 0;
        C = grid.length;
        if(C == 0) return 0;

        UF uf = new UF(R * C + 1);
        for(int v = 0; v < R * C; v ++){
            int x = v / C, y = v % C;
            if(grid[x][y] == 1)
                for(int d = 0; d < 4; d ++){
                    int netx = x + dirs[d][0], nety = y + dirs[d][1];
                    if(inArea(netx, nety) && grid[netx][nety] == 1)
                        uf.unionElements(v, netx*C + nety);
                }
            else
                uf.unionElements(v, R*C);
        }
        return uf.treeNumber();
    }
    private boolean inArea(int x, int y){return x >= 0 && x < R && y >= 0 && y < C;}
}

感觉在这种实现中,关键可能是没有对海那部分做特殊处理,而海部分的索引在并查集中也充当了节点的身份,导致不能直接得到联通分量的具体个数;并且也不像是图dfs遍历那样一口气遍历完一个联通分量,而是每次只遍历一个结点与它的相邻节点,很难使用一个count来对每次遍历进行计数

写回答

1回答

liuyubobobo

2019-09-21

思路是对的。


1)C = grid[0].length;

2)grid 里的元素是 char,不是 int


继续加油。

0
1
martin123_
老师见笑了?
2019-09-21
共1条回复

玩转算法系列--图论精讲(Java版)

30+小时系统学习,bobo带你克服被图论支配的恐惧

1591 学习 · 324 问题

查看课程