您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 1232 暢通工程：並查集統計連通分量

編輯：C++ 入門

問題描述

給定 n 個城鎮、m 條雙向道路。道路連接的兩個城鎮之間可以互通。目標是使任意兩個城鎮間都能互通（不一定直接相連）。求最少還需建設多少條道路。n < 1000，多測試用例，n=0 結束。

解題思路：連通分量計數

現有道路構成若干連通分量。要將 k 個連通分量連成一個整體，最少需要 k-1 條新道路（樹的邊數 = 點數 - 1）。因此問題轉化為：統計無向圖的連通分量個數。

並查集實現

初始化：每個城鎮自成一集 fa[i] = i
合併：對每條路 (a, b)，執行 union(a, b)
統計：掃描 1..n，根節點個數即為連通分量數 cnt
答案：cnt - 1

參考代碼（C++）

#include <iostream>
using namespace std;

const int MAXN = 1010;
int fa[MAXN];

void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i; }
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra != rb) fa[ra] = rb;
}

int main() {
    int n, m;
    while (cin >> n) {
        if (n == 0) break;
        cin >> m;
        init(n);
        for (int i = 0; i < m; i++) {
            int a, b; cin >> a >> b;
            unite(a, b);
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++) if (find(i) == i) cnt++;
        cout << cnt - 1 << endl;
    }
    return 0;
}