Force buckle 1319 Number of connected network operations

subject

Connect... With Ethernet cable n Computers are connected into a network , The number of the computer is from 0 To n-1. For cable connections Express , among connections[i] = [a, b] Connected to the computer a and b.

Any computer in the network can directly or indirectly access any other computer in the same network through the network .

Give you the initial wiring of this computer network connections, You can disconnect the cable between any two directly connected computers , And use it to connect a pair of computers that are not directly connected . Please calculate and return the minimum number of operations required to connect all computers . If not , Then return to -1 .

Example

Input ：n = 4, connections = [[0,1],[0,2],[1,2]]
Output ：1
explain ： Unplug the computer 1 and 2 The cable between , And plug it into the computer 1 and 3 On .

Input ：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output ：2

Input ：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
Output ：-1
explain ： Insufficient number of cables .

Input ：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
Output ：0

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/number-of-operations-to-make-network-connected
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Method 1： Union checking set

Java Realization

Balanced optimization ：size Array . Connect the small tree to the big one
Path compression ：find()

class Solution {
    
    public int makeConnected(int n, int[][] connections) {
    
        if (connections.length < n - 1) return -1;
        UF uf = new UF(n);

        for (int[] con : connections) {
    
            uf.unite(con[0], con[1]);
        }
        return uf.count - 1;
    }

    class UF {
    
        private int count; // The number of connected components 
        int n; // Number of nodes in the graph 
        private int[] parent; // Stores the parent node of each node 

        private int[] size; // Number of each node , Make sure the little tree is under the big tree 

        public UF(int n) {
    
            this.count = n;
            this.parent = new int[n];
            this.size = new int[n];
            Arrays.fill(size, 1);
            for (int i = 0; i < n; i++) {
    
                parent[i] = i;
            }
        }

        // Find the root node of each node 
        public int find(int x) {
    
            if (parent[x] != x) {
    
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        // The nodes x And nodes y connected 
        public boolean unite(int x, int y) {
    
            x = find(x);
            y = find(y);

            if (x == y) return false;

            if (size[x] < size[y]) {
    
                int tmp = x;
                x = y;
                y = tmp;
            }
            parent[y] = x;
            size[x] += size[y];
            count--;
            return true;
        }

        public boolean connected(int x, int y) {
    
            x = find(x);
            y = find(y);
            return x == y;
        }
    }
}