547. 省份数量

并查集套路:

1初始化

2查询(要路径压缩)

3合并

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

代码语言：javascript复制

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

压缩

0 人点赞