题解 | #畅通工程#

#include <iostream>
#include <cstdio>

using namespace std;

/**
 * 元素个数最大值
 */
#define MAX_NUM 1000

/**
 * 父亲节点，存储了每个"节点的父亲节点"的下标索引
 */
int father[MAX_NUM];

/**
 * 树高度；当节点为根节点时，才记录该树的高度
 */
int height[MAX_NUM];

/**
 * 初始化并查集的每个集合
 */
void Init(int n) {
    /**
     * 题目已说明：城镇编号从1到N编号。
     * 最初时，每个元素为一个单独的集合
     */
    for (int i = 1; i <= n; ++i) {
        /*
         * 每个节点就是一棵树，所以节点的父节点下标索引为其本身.
         * 注：初始化时"节点的父节点下标索引为其本身"为自定义，有些教材为-1.
         */
        father[i] = i;
        //树高为1.
        height[i] = 1;
    }
}

/**
 * 优化--路径压缩
 * 查找x节点的祖先，即x节点所在树的根节点
 * @param x x节点
 * @return x节点所在树的根节点
 */
int Find(int x) {
    if (x != father[x]) {
        //不是根节点，递归向上查找.
        //执行完Find操作之后，都会将节点的父节点索引设置为根节点，实现"路径压缩"的效果.
        father[x] = Find(father[x]);
    }
    //当x节点的父节点索引为其本身时时，此时x节点即为根节点.
    return father[x];
}

/**
 * 优化--大树并小树
 * 合并x节点和y节点所在的两个集合
 * @param x x节点
 * @param y y节点
 */
void Union(int x, int y) {
    /**
     * 合并两棵树
     * 1、找到y节点的祖先
     * 2、找到x节点的祖先
     * 3、y节点的祖先的父节点 设置为 x节点的祖先，实现y所在集合并到x所在集合下
     */
    y = Find(y);
    x = Find(x);
    /*
     * 不为同一个集合
     * 矮树作为高树的子树
     */
    if (x != y) {
        if (height[x] < height[y]) {
            //x树低于y树，则将y树作为x树的子树.
            father[x] = y;
        } else if (height[y] < height[x]) {
            father[y] = x;
        } else {
            //两棵树高度一样，合并后记得将树高+1.
            father[y] = x;
            height[x]++;
        }
    }
}


/**
 * 畅通工程--浙江大学
 * @return
 */
int main() {
    int n, m;
    while (cin >> n >> m) {
        if (n == 0) {
            break;
        }
        //初始化.
        Init(n);
        for (int i = 0; i < m; ++i) {
            int x, y;
            cin >> x >> y;
            //合并x顶点和y顶点.
            Union(x, y);
        }
        int ans = 0;
        /*
         * 统计集合的个数
         */
        if (m == 0) {
            //不存在已建成的道路，则最少只需"顶点数-1"条边，即可变为连通图.
            ans = n - 1;
        } else {
            //存在已经建成的道路.
            for (int j = 1; j <= n; ++j) {
                if (j == Find(j)) {
                    ans++;
                }
            }
        }
        cout << ans - 1 << endl;
    }

    return 0;
}