題目描述有n個城市編號1 ~ n和m條雙向道路。每條道路連接兩個城市?，F(xiàn)在要判斷這些城市是否全部連通即任意兩個城市之間都有路徑。如果全部連通輸出YES否則輸出需要最少新增多少條道路才能全部連通。輸入第一行n m1 ≤ n ≤ 10^50 ≤ m ≤ 2×10^5接下來m行每行兩個整數(shù)u v表示一條道路。輸出若已全部連通YES否則一個整數(shù)表示最少新增道路數(shù)。示例text輸入 5 3 1 2 2 3 4 5 輸出 1解釋連通分量為{1,2,3}和{4,5}需要 1 條路連接兩個分量。解題思路用并查集維護(hù)連通分量初始每個城市獨立連通分量數(shù)components n。每合并兩個不同集合components--。最終若components 1輸出YES否則輸出components - 1最少新增道路數(shù) 連通分量數(shù) - 1。參考代碼c#include stdio.h int parent[100005]; int rank_[100005]; int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); // 路徑壓縮 return parent[x]; } int unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return 0; if (rank_[ra] rank_[rb]) { parent[ra] rb; } else if (rank_[ra] rank_[rb]) { parent[rb] ra; } else { parent[rb] ra; rank_[ra]; } return 1; } int main(void) { int n, m; scanf(%d %d, n, m); for (int i 1; i n; i) { parent[i] i; rank_[i] 0; } int components n; for (int i 0; i m; i) { int u, v; scanf(%d %d, u, v); if (unite(u, v)) components--; } if (components 1) printf(YES\n); else printf(%d\n, components - 1); return 0; }