并查集杭电ACM-1232-畅通工程

﹏ヽ暗。殇╰゛Y 2023-07-10 12:38 23阅读 0赞

## 杭电ACM-1232-畅通工程 ##

连接：http://acm.hdu.edu.cn/showproblem.php?pid=1232

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

思路：与上面题思路一样，在并查集中进行合并操作，求出最后剩下多少个组(集合)。这些组之间是互相不可达的。假如有M个组，那其实再需要M-1条连线就可以把他们连接起来了。所以组数 - 1 就是最后答案

## 代码： ##

class UnionFind {
        
        /**
         * 记录并查集对应位置的父亲结点位置
         */
        private int[] parent;
        /**
         * 记录并查集对应结点的重量
         */
        private int[] weight;
        /**
         * 表示并查集的元素个数
         */
        private int size;
        /**
         * 表示并查集中集合的个数(组数)
         */
        private int groups;
     
        public UnionFind(int size) {
        
            this.size = size;
            this.groups = size;
            this.parent = new int[size];
            this.weight = new int[size];
            for (int i = 0; i < size; i++) {
        
                this.parent[i] = i;
                this.weight[1] = 1;
            }
        }
     
        public int find(int element) {
        
            while (element != parent[element]) {
        
                parent[element] = parent[parent[element]];
                element = parent[element];
            }
            return element;
        }
     
        public boolean isConneted(int firstElement, int secondElement) {
        
            return find(firstElement) == find(secondElement);
        }
     
        public void unionElements(int firstElement, int secondElement) {
        
            int firstRoot = find(firstElement);
            int secondRoot = find(secondElement);
            if (firstRoot == secondRoot) {
        
                return;
            }
            if (weight[firstRoot] < weight[secondRoot]) {
        
                parent[firstRoot] = secondRoot;
                weight[secondRoot] += weight[firstRoot];
            } else {
        
                parent[secondRoot] = firstRoot;
                weight[firstRoot] += secondRoot;
            }
     
            this.groups--;
        }
     
        public int getGroups(){
        
            return this.groups;
        }
    }
     
    public class Main {
        
        public static void main(String[] args) {
        
            java.util.Scanner scanner = new java.util.Scanner(System.in);
            int size = scanner.nextInt();
            while(size!=0){
        
                int input = scanner.nextInt();
                UnionFind union = new UnionFind(size);
                for(int i = 0;i<input;i++){
        
                    //因为测试数据中是从1开始技术。而我们的并查集是从0开始，所以每个输入都减1
                    int first = scanner.nextInt() - 1;
                    int second = scanner.nextInt() - 1;
                    union.unionElements(first,second);
                }
                //最后剩下的组数 - 1 就是最后的答案。因为连接M组的话，需要M-1条连线就可以了
                System.out.println(union.getGroups() - 1);
                size = scanner.nextInt();
            }
        }
    }