一、學習目標

• 熟悉 Union-Find（Disjoint Set Union, DSU）：路徑壓縮 + 按大小/秩合併。
• 會用 Kruskal 建立 最小生成樹（MST），並判斷是否可連通。
• 能用 DSU 處理增量連邊、統計連通分量數與最大分量大小。
• 知道 Kruskal vs Prim 的選擇：邊稀疏/可排序 → Kruskal；稠密圖/隱式完全圖 → Prim 較常用。

二、觀念說明（加強版）

什麼是 MST / 何時存在

• 最小生成樹（MST）：在連通無向加權圖中，選出 n−1 條邊把所有點連起來，且總權重最小。
• 不存在情況：圖不連通 → 沒有 spanning tree（只能得到各連通分量的最小生成森林 MSF）。

Kruskal 的正確性（切割性質 & 環性質）

• 切割性質（Cut Property）：對任意將頂點集切成兩邊的「切割」，所有跨越該切割的邊中，權重最小者一定存在於某棵 MST。
  ⇒ 這說明了 Kruskal 「每次選最小且不成環的邊」是安全的（不會失去最優）。
• 環性質（Cycle Property）：對任意一個「環」，權重最大的那條邊不會在某棵 MST 中（若權重唯一，更強：不可能在任何 MST）。
  ⇒ 若加入一條邊形成環，去掉環中最重邊不劣化，能維持連通性與（不增）總權。

Kruskal 流程與複雜度

• 將所有邊依權重升序排序。
• 依序嘗試加入邊，若兩端點屬於不同集合（不會形成環），就把它加入 MST，並在 DSU 中合併。
• 收滿 n−1 條邊即完成。若最後不足 n−1，代表不連通。
• 時間複雜度：排序 O(mlogm) + DSU 幾乎常數（α(n)）→ 整體 O(mlogm)。

Union-Find（DSU）為何快

• 路徑壓縮：find(x) 時把沿途父節點直接指向根，壓平樹高。
• 按大小/秩合併：小樹接到大樹，避免退化。
• 攤還複雜度：單次操作近似 O(1)，更精確為 α(n)（反阿克曼函數）。

Kruskal vs Prim 何時用

• Kruskal：邊可一次拿到、易排序、圖稀疏（m≈n）時佳；也常用在幾何/離線類題。
• Prim（堆版）：圖稠密/隱式完全圖（如幾何完全圖），或只需鄰接查詢；複雜度 O(mlogn)

三、CSES實戰演練

題目1:Road Reparation

原題:
https://cses.fi/problemset/task/1675

題意:
有 n 城市與m 條雙向道路候選，每條路有修復成本。要把所有城市連通且總成本最小；若無法連通，輸出 IMPOSSIBLE。

解題思路

• 典型 Kruskal + DSU。
• 將所有邊依成本排序，能合併就加邊並累積總成本。
• 最後若合併次數 =n−1 成功，輸出成本；否則 IMPOSSIBLE。
• 時間複雜度：O(mlogm)。

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, sz;
    DSU(int n=0){ init(n); }
    void init(int n){
        p.resize(n+1); sz.assign(n+1,1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    bool unite(int a,int b){
        a=find(a); b=find(b);
        if(a==b) return false;
        if(sz[a]<sz[b]) swap(a,b);
        p[b]=a; sz[a]+=sz[b];
        return true;
    }
};

int main(){
    int n, m;
    cin>>n>>m;
    struct E{int u,v; long long w;};
    vector<E> edges(m);
    for(auto &e: edges) cin>>e.u>>e.v>>e.w;
    sort(edges.begin(), edges.end(), [](const E&a,const E&b){return a.w<b.w;});
    DSU dsu(n);
    long long cost=0; int used=0;
    for(auto &e: edges){
        if(dsu.unite(e.u,e.v)){
            cost+=e.w; used++;
            if(used==n-1) break;
        }
    }
    if(used==n-1) cout<<cost<<"\n";
    else cout<<"IMPOSSIBLE\n";
    return 0;
}

題目2:Road Construction

原題:
https://cses.fi/problemset/task/1676

題意:
給 n 個城市，逐一加入 m 條無向邊。每加入一條邊後，輸出：

1. 當前連通分量數
2. 最大分量大小。

解題思路:
用 DSU 維護集合大小與分量數。
初始化分量數 = n，最大分量 = 1。每次 unite(u,v) 成功就分量數 -1、更新最大分量。
複雜度：O((n+m)α(n))。

#include <bits/stdc++.h>
using namespace std;

struct DSU{
    vector<int> p, sz;
    DSU(int n=0){ init(n); }
    void init(int n){
        p.resize(n+1); sz.assign(n+1,1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    bool unite(int a,int b, int &mx){
        a=find(a); b=find(b);
        if(a==b) return false;
        if(sz[a]<sz[b]) swap(a,b);
        p[b]=a; sz[a]+=sz[b];
        mx = max(mx, sz[a]);
        return true;
    }
    int size(int x){ return sz[find(x)]; }
};

int main(){
    int n, m;
    cin>>n>>m;
    DSU dsu(n);
    int comps = n, mx = 1;
    while(m--){
        int u,v; cin>>u>>v;
        if(dsu.unite(u,v,mx)) comps--;
        cout << comps << " " << mx << "\n";
    }
    return 0;
}

四、Leetcode實戰演練

題目1:Min Cost to Connect All Points

原題:
https://leetcode.com/problems/min-cost-to-connect-all-points/description/

題意:
有 n 個點，連線成本為曼哈頓距離，求連通全部點的最小成本。

解題思路:
這是完全圖的 MST。可用 Prim。
示範 Kruskal：
生成所有邊（至多 n(n−1)/2 條，n=1000 時約 50 萬），排序後用 DSU 選邊。

class Solution {
public:
    struct DSU{
        vector<int> p, sz;
        DSU(int n=0){ init(n); }
        void init(int n){ p.resize(n); sz.assign(n,1); iota(p.begin(),p.end(),0); }
        int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
        bool unite(int a,int b){
            a=find(a); b=find(b);
            if(a==b) return false;
            if(sz[a]<sz[b]) swap(a,b);
            p[b]=a; sz[a]+=sz[b];
            return true;
        }
    };
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        struct E{int w,u,v;};
        vector<E> edges; edges.reserve(n*(n-1)/2);
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int w = abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1]);
                edges.push_back({w,i,j});
            }
        }
        sort(edges.begin(), edges.end(), [](const E&a,const E&b){return a.w<b.w;});
        DSU dsu(n);
        long long ans=0; int used=0;
        for(auto &e: edges){
            if(dsu.unite(e.u,e.v)){
                ans+=e.w; used++;
                if(used==n-1) break;
            }
        }
        return (int)ans;
    }
};

題目2:Number of Operations to Make Network Connected

原題:
https://leetcode.com/problems/number-of-operations-to-make-network-connected/description/

題意:
有 n 台電腦與一些無向連線 connections[i] = [u, v]。
一次操作可以把多餘的線（即在同一連通分量內造成多餘、可移除的邊）重新接到兩個不同分量之間。
問最少需要幾次操作使整體連通；若不可能則回傳 -1。

解題思路:

• 必要條件：要連通 n 個點至少需要 n−1 條邊。若 m < n-1 直接 -1。
• 若邊數足夠，只要數連通分量數 = comps，答案就是 comps - 1。理由：把每個分量接起來需 comps-1 條邊；多餘邊可重接填補。
• 用 DSU 計分量數（find 根的數量）。

class Solution {
public:
    struct DSU{
        vector<int> p, sz;
        DSU(int n=0){ init(n); }
        void init(int n){ p.resize(n); sz.assign(n,1); iota(p.begin(), p.end(), 0); }
        int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
        bool unite(int a,int b){
            a=find(a); b=find(b);
            if(a==b) return false;
            if(sz[a]<sz[b]) swap(a,b);
            p[b]=a; sz[a]+=sz[b];
            return true;
        }
    };

    int makeConnected(int n, vector<vector<int>>& connections) {
        int m = (int)connections.size();
        if(m < n-1) return -1;           // 邊不夠，必然無解
        DSU dsu(n);
        for(auto &e: connections) dsu.unite(e[0], e[1]);
        int comps = 0;
        for(int i=0;i<n;i++) if(dsu.find(i)==i) comps++;
        return comps - 1;                 // 需要把分量接起來
    }
};