java-畅通工程某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。

Question

import java.util.Scanner;
public class Main {
    static class Union{
        private int parent[];//当前节点给的父节点
        private int count;//连通分量中节点的个数
        public Union(int count){
            parent = new int[count+1];
            this.count = count;
            for (int i = 1; i <= count; i++) {
                parent[i] = i;//使每个节点指向自己，即不再任何集合中
            }
        }
        int find(int p){
        return p == parent[p] ? p : find(parent[p]);
        }
        void unionElements(int p,int q){
            int pRoot = find(p);
            int qRoot = find(q);
            if (pRoot==qRoot){
                return;
            }
            parent[pRoot] = qRoot;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter pr = new PrintWriter(System.out);
        int count = 0;
        while (sc.hasNext()){
            count = 0;
            int n = sc.nextInt();//代表多少个城镇
            if (n==0) break;
            int m = sc.nextInt();//代表有多少条路
            Union union = new Union(n);//城市下标从1开始
            //接下来输入道路，并连接城市
            for (int i = 0; i < m; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                union.unionElements(x,y);//连接城市
            }
            for (int i = 1; i <= n; i++) {
                if (union.parent[i]==i){//父节点没有变的，就是未接通的
                    count++;
                }
            }
            System.out.println(count-1);
        }


    }

}

Answer 1

简单的并查集问题