并查集练习——省份数量

简介: 并查集练习——省份数量

力扣原题链接:省份数量

有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ,其中 isConnectedi = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnectedi = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1:

输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出:2
示例 2:

输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出:3

提示:

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnectedi 为 1 或 0
isConnectedi == 1
isConnectedi == isConnectedj

package com.harrison.class10;

/**
 * @author Harrison
 * @create 2022-03-19-13:11
 * @motto 众里寻他千百度,蓦然回首,那人却在灯火阑珊处。
 */
public class Code02_FriendCircles {
    // https://leetcode.com/problems/friend-circles/
    public static class UnionFind{
        // parent[i]=k i的父亲是K
        public int[] parent;
        // size[i]=k 如果i是代表结点,size[i]才有意义,否则无意义
        // i所在的集合大小是k
        public int[] size;
        // 辅助结构
        public int[] help;
        // 一共有多少个集合
        public int sets;

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

        // 从i开始往上,往上到不能再往上,就是代表结点,返回
        // 这个过程要做路径压缩
        public int find(int i){
            int hi=0;
            while (i!=parent[i]){
                help[hi++]=i;
                i=parent[i];
            }
            for(hi--; hi>=0; hi--){
                parent[help[hi]]=i;
            }
            return i;
        }

        public void union(int i,int j){
            int f1=find(i);
            int f2=find(j);
            if(f1!=f2){
                if(size[f1]>=size[f2]){
                    size[f1]+=size[f2];
                    parent[f2]=f1;
                }else{
                    size[f2]+=size[f1];
                    parent[f1]=f2;
                }
                sets--;
            }
        }

        public int sets(){
            return sets;
        }
    }

    public static int findCircleNum(int[][] isConnected){
        int N=isConnected.length;
        // {0} {1} {2} {3}...{N-1}
        UnionFind unionFind=new UnionFind(N);
        for(int i=0; i<N; i++){
            for(int j=i+1; j<N; j++){
                if(isConnected[i][j]==1){// i和j互相认识
                    unionFind.union(i,j);
                }
            }
        }
        return unionFind.sets;
    }
}
相关文章
|
6月前
|
算法 测试技术 C#
C++二分查找:统计点对的数目
C++二分查找:统计点对的数目
|
6月前
leetcode-6133:分组的最大数量
leetcode-6133:分组的最大数量
52 0
|
人工智能 BI 索引
【Leetcode -598.范围求和Ⅱ -599.两个列表的最小索引总和】
【Leetcode -598.范围求和Ⅱ -599.两个列表的最小索引总和】
43 0
|
6月前
|
算法 测试技术 C#
【最大值线段树】【二分查找】2286. 以组为单位订音乐会的门票
【最大值线段树】【二分查找】2286. 以组为单位订音乐会的门票
|
6月前
leetcode-547:省份数量
leetcode-547:省份数量
48 0
|
人工智能 编译器 BI
[蓝桥杯 2018 省 B]递增三元组
[蓝桥杯 2018 省 B]递增三元组
136 0
每日三题-岛屿数量、合并二叉树、课程表
每日三题 岛屿数量 合并二叉树 课程表
54 1
每日三题-岛屿数量、合并二叉树、课程表
|
索引 Python
LeetCode 599. 两个列表的最小索引总和
假设Andy和Doris想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。
93 0
|
机器学习/深度学习
LeeCode 547. 省份数量(DFS)
LeeCode 547. 省份数量(DFS)
68 0