题解 | #城市群数量#并查集做法

并查集

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param m int整型ArrayList<ArrayList<>> 
     * @return int整型
     */
    public int citys (ArrayList<ArrayList<Integer>> m) {
        // write code here
        if(m.size()==1) return 1;
        UF uf=new UF(m.size());
        // 遍历邻接矩阵
        for(int i=0;i<m.size();i++){
            for(int j=0;j<m.get(0).size();j++){
                if(i==j) continue;
                if(m.get(i).get(j)==1){
                    // 把i和j连通
                    uf.union(i,j);
                }
            }
        }
        // 返回连通分量
        return uf.count();
        
    }
    
    class UF{
        int count; // 连通分量
        int[] parent; // 记录父节点
        // 构造函数,n为结点个数
        UF(int n){
            this.count=n; // 初始连通分量
            this.parent=new int[n];
            for(int i=0;i<n;i++){
                parent[i]=i;  // 初始父节点指向自己
            }
        }
        // 找到x的根节点
        int find(int x){
            while(parent[x]!=x){
                x=parent[x];
            }
            return x;
        }
        // 连接p和q
        void union(int p, int q){
            int rootQ=find(q);
            int rootP=find(p);
            if(rootP!=rootQ){
                parent[rootP]=rootQ;
                count--;
            }            
        }
        // 返回连通分量
        int count(){
            return count;
        }
    }
}