最小生成树 - 还是畅通工程

这是一道典型的最小生成树的题目， 利用Kruskal算法，先按照road的长度排序，若当前的road未在连接好的“城市组”里，则连通它。直到所有的城市全部连通，即所铺路径最短。

// runtime: 6ms
// space: 488K
#include <iostream>
#include <algorithm>
using namespace std;

struct Road {
    int from;
    int to;
    int distance;

    bool operator< (const Road& r) const {
        return distance < r.distance;
    }
};

const int MAX = 100;

Road road[MAX * MAX];
int father[MAX];
int height[MAX];
// 并查集代码
void Initial(int n) {
    for (int i = 0; i <= n; ++i) {
        father[i] = i;
        height[i] = 0;
    }
}

int Find(int x) {
    if (x != father[x]) {
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x != y) {
        if (height[x] > height[y]) {
            father[y] = x;
        } else if (height[x] < height[y]) {
            father[x] = y;
        } else {
            father[x] = y;
            height[y]++;
        }
    }
}

int Kruskal(int cityNum, int roadNum) {
    Initial(cityNum);

    sort(road, road + roadNum);
    int sum = 0;
    for (int i = 0; i < roadNum; ++i) {
        Road current = road[i];
        if (Find(current.from) != Find(current.to)) { // 核心代码
            Union(current.from, current.to);
            sum += current.distance;
        }
    }
    return sum;
}

int main() {
    int cityNum;
    while (cin >> cityNum) {
        if (cityNum == 0)
            break;

        int roadNum = cityNum * (cityNum - 1) / 2;
        for (int i = 0; i < roadNum; ++i) {
            cin >> road[i].from >> road[i].to >> road[i].distance;
        }

        cout << Kruskal(cityNum, roadNum) << endl;
    }
    return 0;
}