鏈接：https://www.luogu.com.cn/problem/P1536

創(chuàng)新互聯(lián)堅持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的游仙網(wǎng)站設(shè)計、移動媒體設(shè)計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！題目描述

某市調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計表。表中列出了每條道路直接連通的城鎮(zhèn)。市政府 "村村通工程" 的目標(biāo)是使全市任何兩個城鎮(zhèn)間都可以實現(xiàn)交通（但不一定有直接的道路相連，只要相互之間可達(dá)即可）。請你計算出最少還需要建設(shè)多少條道路？

代碼：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            //村莊數(shù)
            int num = sc.nextInt();
            if(num != 0) {
                UnionFind unionFind = new UnionFind(num);
                //路的數(shù)量
                int roads = sc.nextInt();
                for (int i = 0; i< roads; i++) {
                    int x = sc.nextInt();
                    int y = sc.nextInt();
                    unionFind.union(x, y);
                }
                //最少建設(shè)的道路數(shù)量 ->村中心數(shù) - 1
                int min_roads = unionFind.sets() - 1;
                System.out.println(min_roads);
            }
        }
        
    }
}

class UnionFind {
    HashMapvillage;
    //集合數(shù) -- 多少個村中心
    private int sets;
    
    public UnionFind(int n) {
        //初始化，視 每個村莊都是獨(dú)立的（村中心）
        sets = n;
        village = new HashMap<>();
        for (int i = 1; i< n; i++) {
            village.put(i, null);
        }
    }
    
    public int findVillageCenter(int x) {
        int center = x;
        //找 村中心
        while (village.get(center) != null) {
            center = village.get(center);
        }
        //壓縮路徑 -- 登記村莊的村中心
        while (village.get(x) != null) {
            int old = village.get(x);
            village.put(x, center);
            x = old;
        }
        return center;
    }
    
    //將兩個村中心 連通
    public void union(int x, int y) {
        int centerX = findVillageCenter(x);
        int centerY = findVillageCenter(y);
        
        if (centerX != centerY) {
            sets--;
            village.put(centerX, centerY);
        }
    }
    //返回村中心的數(shù)量
    public int sets() {
        return sets;
    }
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱：洛谷P1536村村通(java,并查集)-創(chuàng)新互聯(lián)
瀏覽地址：http://weahome.cn/article/csjehg.html