題意#
Byteland 有 \(n\) 座城市，目前城市之間已經蓋好了 \(m\) 條道路。我們的目標是希望所有城市都能夠互相連通（可以直接或間接抵達任何一座城市）。
你需要計算出：為了達成這個目標，我們「最少需要再建造幾條新道路」？並且具體給出一組應該建造的道路清單。
思路#
這題的核心概念就是要把所有原本各自為政的「連通塊（Connected Components）」給串接起來。
如果在整張地圖上，我們目前有 \(K\) 個分開的獨立連通塊，要把它們全部連成一條線（確保全部連通），最少就只需要再蓋 \(K - 1\) 條道路。
要尋找並合併這些連通塊，最直覺也最大多數人會使用的方法就是「互斥集（Disjoint Set Union, DSU）」。只要讀進一條現成的道路，我們就把這兩個端點做一次合併操作。當所有給定的邊都處理完之後，我們就能輕鬆找出所有剩下的連通塊各自的「老大（代表節點）」。
最後，只要將這幾個連通塊的代表節點兩兩相連，就能以最少的道路數量完成 Byteland 全島貫通的目標了。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
vector<int> anc; // 儲存每個節點的老大（祖先）
// DSU Find 操作：尋找節點的最終老大，並透過路徑壓縮（Path Compression）加速未來查詢
int Find(int x) {
return x == anc[x] ? x : anc[x] = Find(anc[x]);
}
// DSU Union 操作：合併兩個集合
void Union(int a, int b) {
a = Find(a), b = Find(b);
if (a == b) return; // 本來就屬於同一個連通塊
if (a > b) swap(a, b);
anc[b] = a; // 將編號較大的老大歸順於編號較小的老大
}
signed main() { WA();
int n, m; cin >> n >> m;
anc.assign(n, 0);
iota(all(anc), 0); // 初始時，每個節點的老大都是自己
// 讀入所有已經建好的道路，並試著將兩端的城市合併
while (m--) {
int a, b; cin >> a >> b;
a--, b--; // 將 1-based 的輸入轉換成 0-based
Union(a, b);
}
// 用 set 來把所有連通塊的最終代表節點收集起來，過濾掉重複的元素
set<int> st;
for (auto &i : anc) st.insert(Find(i));
// 將 set 中的元素倒進 vector，方便後續依序輸出
vector<int> ans;
for (auto &i : st) ans.pb(i);
// 需要加蓋的道路數量等於：連通塊數量 - 1
cout << st.size()-1 << '\n';
// 依序將相鄰的代表節點連接起來（輸出時要記得加回 1 變成 1-based）
for (int i = 0; i+1 < ans.size(); i++) cout << ans[i]+1 << ' ' << ans[i+1]+1 << '\n';
}
