POJ-1251-Jungle Roads-最小生成树-Kruskal算法

题意
给定一个图，求其最小生成树。
解决
参考《算法导论》里面Kruskal算法的讲解，使用“并查集”这种数据结构，去生成最小生成树。
心得
这道题太爽了，一次就AC了。原因是由于之前在解题时写过并查集，现在直接套用却可，省了不少功夫。关于并查集，还可参考“POJ 1611 The Suspects 解题报告”。
代码

#include <algorithm>
#include <iostream>
using namespace std;

const int MAX_VIL_SIZE = 30;
const int MAX_EDGE_SIZE = 80;

struct Edge {
    int begin; //边的起始结点，以下标表示，下标从0开始
    int end; //边的结束结点
    int weight; //边的权值
};

int parent[MAX_VIL_SIZE]; //各个结点的“根”;从下标0开始存储
int num[MAX_VIL_SIZE]; //各个结点“轶”
Edge edges[MAX_EDGE_SIZE];

void initSet(int n); /*初始化并查集*/
unsigned int find(int x); /*查找结点x的“根”*/
void unionSet(int a, int b); /*合并结点a和结点b*/

bool cmp(const Edge &a, const Edge &b); /*sort所使用的比较函数*/

int main()
{
    int n;
    while(cin >> n, n != 0) {
        int edgesNum = 0;

        /*接下来的n-1行输入*/
        for(int i = 0; i < n - 1; i++) {
            char beginChar, endChar;
            cin >> beginChar;
            int nAdj;
            cin >> nAdj;
            int w;
            for(int j = 0; j < nAdj; j++) {
                cin >> endChar >> w;
                edges[edgesNum].begin = beginChar - 'A';
                edges[edgesNum].end = endChar - 'A';
                edges[edgesNum].weight = w;
                edgesNum++;
            }
        }

        /*对所有边根据weight从小到大排序*/
        sort(edges, edges + edgesNum, cmp);

        /*初始化并查集*/
        initSet(n);

        int minWeight = 0;
        /*Kruskal算法*/
        for(int i = 0; i < edgesNum; i++) {
            int beginIndex = edges[i].begin;
            int endIndex = edges[i].end;
            if(find(beginIndex) != find(endIndex)) {
                unionSet(beginIndex, endIndex);
                minWeight += edges[i].weight;
            }
        }

        cout << minWeight << endl;
    }

    return 0;
}

bool cmp(const Edge &a, const Edge &b) {
    return a.weight < b.weight;
}

void initSet(int n) {
    for(int i = 0; i < n; i++) {
        parent[i] = -1;
        num[i] = 1;
    }
}

unsigned int find(int x) {
    int r = x;
    while(parent[r] != -1)
        r = parent[r];

    int temp;
    while(x != r) {
        temp = parent[x];
        parent[x] = r;
        x = temp;
    }

    return r;
}

void unionSet(int a, int b) {
    a = find(a);
    b = find(b);
    if(a == b) return ;

    if(num[b] > num[a]) {
        parent[a] = b;
        num[b] += num[a];
    } else {
        parent[b] = a;
        num[a] += num[b];
    }
}