題意#
一開始有 \(n\) 座孤立的城市完全沒有任何交集。在接下來的這 \(m\) 天裡，每天都會有兩座特定城市之間建好一條新道路。
每建好一條道路，都可能會讓原本各自為政的幾座城市「連成一大塊（連通塊）」。你的任務是，在每一天道路建好之後，立刻回報目前的兩個關鍵數據：
- 世界上總共還剩下幾個獨立的連通塊？
- 在這些連通塊當中，包含最多城市的那個連通塊，裡面有幾座城市？
思路#
這是一道設計來展現「互斥集（Disjoint Set Union, DSU）」動態維護能力的經典題。如果大家有印象，我們在求最小生成樹或是連通塊數量時，DSU 本來就是一把利器。但這題額外要求我們「隨時知道最大塊的尺寸」。
為了解決這個問題，我們除了要準備一個用來認老大的 anc 陣列外，還需要額外多開一個 sz 陣列來記錄：「每個連通塊老大底下到底管了多少座城市」。
一開始有 \(n\) 座城市，就等於有 \(n\) 個大小為 1 的連通塊。每當一天新道路蓋好，我們就試圖將道路兩端的城市做一次 Union 合併。
- 如果這兩座城市的最終老大真的不一樣，合併時除了小弟要改認新老大，原本那塊的城市總數
sz[小老大]也會被全部併吞加進sz[大老大]裡面。 - 一旦成功併吞（Union），就代表又少了一個獨立勢力，總連通塊數量直接減一。
- 我們再順手用一個變數維護「歷史最大塊」的紀錄，只要哪個老大吞併後規模超越了這個數字，就立刻刷新紀錄。
整趟跑下來，不管是合併或是尋找老大，靠著路徑壓縮的均攤時間幾乎等同於常數 \(O(1)\)，非常輕快俐落。
程式碼#
#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, sz;
int mx = 1; // 記錄全場最龐大的連通塊尺寸，初始每個城市自成一國所以是 1
// 尋找總老大，附帶路徑壓縮把整串沿路的節點直接指派給總老大
int Find(int x) {
return x == anc[x] ? x : anc[x] = Find(anc[x]);
}
// 嘗試合併兩個城市的地盤
bool Union(int a, int b) {
a = Find(a), b = Find(b);
if (a == b) return false; // 早就互通了，不用合併也不影響紀錄
if (a > b) swap(a, b);
// b 歸順於 a，a 接收 b 的所有領土與人民
// 成功擴充後，順便挑戰一下是否打破了歷史最大的連通塊紀錄 mx
return anc[b] = a, sz[a] += sz[b], mx = max(mx, sz[a]), true;
}
signed main() { WA();
int n, m; cin >> n >> m;
anc.assign(n+1, 0); // 老大陣列
sz.assign(n+1, 1); // 領土尺寸陣列預設每塊為 1
iota(all(anc), 0);
while (m--) {
int a, b; cin >> a >> b;
// 若合併成功，世界上獨立的區塊數 n 就會少一個
if (Union(a, b)) n--;
// 每天直接輸出當下的剩餘區塊數，以及我們維護的全場最大尺寸
cout << n << ' ' << mx << '\n';
}
}
