题解 | #畅通工程#

#include <bits/stdc++.h>
#include <vector>
using namespace std;
int city_num, road_num;
int one_city, another_city;
int a, b;
int single;
int main() {
    while (cin >> city_num &&
            city_num) { // 当城镇数目为0时，输入结束，该用例不被处理。
        cin >> road_num;
        vector<int> root(city_num + 1, -1); //所有人的祖先都初始化为-1
        single = city_num; //一开始所有城市，每个城市都是一个个体
        while (road_num--) {
            cin >> one_city >> another_city; //输入两个城市
            //看看这两个城市在不在一个集合
            a = one_city;
            b = another_city;
            while (root[a] != -1) a = root[a];
            while (root[b] != -1) b = root[b];
            //不在一个集合，所以要合并
            if (a != b) {
                root[a] = b; //这一步就是合并，写root[b]=a也可
                single--;//至少有两个城市进行了合并，那么合并的这两个城市可以看作新的一个个体，总的来说数量少了一个，合二为一
            } else continue; //在一个集合，不需要合并，同时说明这个边的加入对single数量不影响
        }
        cout << single - 1 <<
             endl; //将所有边处理完毕以后剩下single个独立个体，遵循n个顶点最少n-1条边的原则
    }
}
// 64 位输出请用 printf("%lld")