编辑代码

import java.util.Scanner;

public class Main {

    // 并查集数据结构
    static class UnionFind {
        private int[] parent;
        private int[] rank;

        // 初始化并查集
        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        // 查找根节点
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);  // 路径压缩
            }
            return parent[x];
        }

        // 合并两个节点
        public boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                // 按秩合并
                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
                return true;
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 输入n和m
        int n = scanner.nextInt();  // 计算机数量
        int m = scanner.nextInt();  // 线缆数量
        
        // 初始化并查集
        UnionFind uf = new UnionFind(n);
        
        int extraCables = 0;  // 统计冗余连接数量
        
        // 输入m条线缆连接
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            // 如果a和b已经连通,则这是冗余连接
            if (!uf.union(a, b)) {
                extraCables++;
            }
        }
        
        // 统计连通分量数量
        int connectedComponents = 0;
        for (int i = 0; i < n; i++) {
            if (uf.find(i) == i) {
                connectedComponents++;
            }
        }
        
        // 需要的最少操作次数是连通分量数量减1
        int requiredCables = connectedComponents - 1;
        
        // 如果冗余连接足够多,返回需要的操作次数,否则返回-1
        if (extraCables >= requiredCables) {
            System.out.println(requiredCables);
        } else {
            System.out.println(-1);
        }
        
        scanner.close();
    }
}