使用并查集解决的相关问题

虚幻大学 xuhss 313℃ 0评论

? 优质资源分享 ?

学习路线指引(点击解锁) 知识定位 人群定位
? Python实战微信订餐小程序 ? 进阶级 本课程是python flask+微信小程序的完美结合,从项目搭建到腾讯云部署上线,打造一个全栈订餐系统。
?Python量化交易实战? 入门级 手把手带你打造一个易扩展、更安全、效率更高的量化交易系统

作者: Grey

原文地址:使用并查集解决的相关问题

关于并查集的说明,见如下博客:

使用并查集处理集合的合并和查询问题

相关题目

本题的解题思路参考博客

使用DFS和并查集方法解决岛问题

主要思路

横纵坐标表示的是城市,因为城市是一样的,所以只需要遍历对角线上半区或者下半区即可,如果某个(i,j)位置是1,可以说明如下两个情况

第一,i这座城市和j这座城市可以做union操作。

第二,(j,i)位置一定也是1。

遍历完毕后,返回整个并查集中的集合数量即可。

完整代码

public static int findCircleNum(int[][] m) {
        int n = m.length;
        UF uf = new UF(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (m[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        return uf.setSize();
    }

    public static class UF {
        int[] parent;
        int[] help;
        int[] size;
        int sets;

        public UF(int n) {
            size = new int[n];
            parent = new int[n];
            help = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
            sets = n;
        }

        public void union(int i, int j) {
            if (i == j) {
                return;
            }
            int p1 = find(i);
            int p2 = find(j);
            if (p2 != p1) {
                int size1 = size[p1];
                int size2 = size[p2];
                if (size1 > size2) {
                    parent[p2] = p1;
                    size[p1] += size2;
                } else {
                    parent[p1] = p2;
                    size[p2] += size1;
                }
                sets--;
            }
        }

        public int find(int i) {
            int hi = 0;
            while (i != parent[i]) {
                help[hi++] = i;
                i = parent[i];
            }
            for (int index = 0; index < hi; index++) {
                parent[help[index]] = i;
            }
            return i;
        }

        public int setSize() {
            return sets;
        }
    }

待更新...

更多

算法和数据结构笔记

转载请注明:xuhss » 使用并查集解决的相关问题

喜欢 (0)

您必须 登录 才能发表评论!