畅通工程

#include <cstring>
#include <iostream>
#include <set>
using namespace std;
#define _for(i, a, b) for(int i = a; i < b; i++)
const int N = 1000;
int father[N];
int ranks[N];
 //查找：findFather函数返回元素x所在集合的根结点
int findFather(int x){
    int a = x;
    while(father[x] != -1){//如果不是根结点，继续循环
        x = father[x];
    }
    //到这里，x存放的是根结点。下面把路径上的所有结点的father都改成根结点
    while(father[a] != -1){
        int z = a;//因为a要被father[a]覆盖，所以先保存a的值，以修改father[a]
        a = father[a];//a回溯父亲结点
        father[z] = x;//将原先的结点a的父亲改为根结点x
    }
    return x;
}
void Union(int a, int b){
    int faA = findFather(a);//查找a的根结点，记为faA
    int faB = findFather(b);//查找b的根结点，记为faB
    if(ranks[faA] < ranks[faB]){
        father[faA] = faB;
    }else if(ranks[faB] < ranks[faA]){
        father[faB] = faA;
    }else if(faA != faB){
        father[faA] = faB;
        ranks[faB] += 1;
    }
}
int main(){
    //初始化
    int n, m;//结点数目：n 连线数目: m
    while(~scanf("%d", &n) && n){
        scanf("%d", &m);
        _for(i, 1, n + 1) {father[i] = -1; ranks[i] = 1;}
        while(m--){
            int a, b;
            scanf("%d %d", &a, &b);
            Union(a, b);
        }
        int ans = 0;//获取当前集合数量
        _for(i, 1, n + 1){
            if(father[i] == -1)
                ans++;
        }
        printf("%d\n", ans - 1);
    }
    return 0;
}