题目描述有n个城市编号1 ~ n和m条双向道路。每条道路连接两个城市。现在要判断这些城市是否全部连通即任意两个城市之间都有路径。如果全部连通输出YES否则输出需要最少新增多少条道路才能全部连通。输入第一行n m1 ≤ n ≤ 10^50 ≤ m ≤ 2×10^5接下来m行每行两个整数u v表示一条道路。输出若已全部连通YES否则一个整数表示最少新增道路数。示例text输入 5 3 1 2 2 3 4 5 输出 1解释连通分量为{1,2,3}和{4,5}需要 1 条路连接两个分量。解题思路用并查集维护连通分量初始每个城市独立连通分量数components n。每合并两个不同集合components--。最终若components 1输出YES否则输出components - 1最少新增道路数 连通分量数 - 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; }