Leetcode-1319. 连通网络的操作次数

1319. 连通网络的操作次数
用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
输出：2

示例 3：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
输出：-1
解释：线缆数量不足。
示例 4：

输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
输出：0
运行结果

解题思路
利用并查集遍历已有的网线
如果两个计算机已经在一个网络中，则可以拔掉网线--一共可以拔掉num根
如果不在，则将其合并
最后得到并查集的连通域count
需要的网线数为count-1
如果num不够，返回-1
否则返回count-1
java代码

class Solution {
    public int makeConnected(int n, int[][] connections) {
        if(connections.length == 0) return -1;
        UF uf=new UF(n);
        int m=connections.length;
        int num=0;//表示可以拔掉的网线数
        for(int i=0;i<m;i++){
            int a=connections[i][0];
            int b=connections[i][1];
            if(uf.connected(a,b)){
                num++;
            }
            else{
                uf.union(a,b);
            }
        }
        int count=uf.count();
        if(num >= count-1){
            return count-1;
        }
        return -1;
    }
    class UF{
        private int[] parent;
        private int[] size;
        private int count;
        public UF(int n){
            parent=new int[n];
            size=new int[n];
            count=n;
            for(int i=0;i<n;i++){
                parent[i]=i;
                size[i]=1;
                count=n;
            }
        }
        public void union(int a,int b){
            int roota=find(a);
            int rootb=find(b);
            if(roota == rootb) return;
            if(size[roota]>size[rootb]){
                parent[rootb]=roota;
                size[roota]+=size[rootb];
                count--;
            }
            else{
                parent[roota]=rootb;
                size[rootb]+=size[roota];
                count--;
            }
        }
        public int find(int x){
            while(parent[x] != x){
                parent[x]=parent[parent[x]];
                x=parent[x];
            }
            return x;
        }
        public boolean connected(int a,int b){
            int roota=find(a);
            int rootb=find(b);
            return roota == rootb;
        }
        public int count(){
            return count;
        }
    }
}