547. 省份数量

Love The Way You Lie 2022-10-08 05:44 45阅读 0赞

**并查集套路:**

**1初始化**

**2查询(要路径压缩)**

**![2021062013251130.png][]**

**3合并**

> 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
> 
> 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
> 
> 给你一个 n x n 的矩阵 isConnected ，其中 isConnected\[i\]\[j\] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected\[i\]\[j\] = 0 表示二者不直接相连。
> 
> 返回矩阵中 省份 的数量。
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]

class Solution {
        public int findCircleNum(int[][] isConnected) {
            int res=0;
            int [] parent=new int[isConnected.length];
            //1 初始化
            for(int i=0;i<parent.length;i++){
                parent[i]=i;
            }
            for(int i=0;i<isConnected.length;i++){
                for(int j=0;j<isConnected[0].length;j++){
                    if(isConnected[i][j]==1){
                         union(parent,i,j);   
                    }
                }
            }
    
            for(int i=0;i<parent.length;i++){
                if(parent[i]==i){
                    res++;
                }
            }
            return res;
    
        }
        public void union(int []parent,int index1,int index2){//2合并
            parent[find(parent,index1)]=find(parent,index2);//index1的父节点指向index2
        }
        public int find(int [] parent,int index){
            if(index!=parent[index]){
                 parent[index]=find(parent,parent[index]);//当前节点的父节点=找当前节点的父节点
            }
            return parent[index];
          
        }
    }

[2021062013251130.png]: /images/20221005/38bfeedcf8ff44fcb571e83a973b3a2f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221005/e3ff807e8bb04cff86b17a0ab434f1bb.png