题解 | Jungle Roads

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef struct Edge { //边结点的信息
    char u;
    char v;
    int weight;
    Edge(char u1, char v1, int weight1) { //构造函数
        u = u1;
        v = v1;
        weight = weight1;
    }
};
map<char, char>
father; //字符/字符串作为顶点编号需要用map才能实现！
char FindDisjointSet(char u) { //压缩路径查找和初始化一起进行
    if (father.find(u) != father.end()) { // u结点的已经初始化的情况下
        if (father[u] != u) { //非根结点
            father[u] = FindDisjointSet(
                            father[u]); //将当前结点的父结点直接指向当前集合的根！
        }
    } else { // u结点的未初始化的情况下 其父亲结点等于本身
        father[u] = u;
    }
    return father[u]; //返回u结点的父节点（根）
}
void UnionDisjointSet(char u, char v) { //将结点v合并到结点u 顶点
    char uroot = FindDisjointSet(u); //寻找u的根（最上面的祖先结点）
    char vroot = FindDisjointSet(v);//寻找v的根（最上面的祖先结点）
    father[vroot] = uroot; //v的父亲结点指向u结点
}
bool compare( Edge lhs, Edge rhs) { //按权值进行排序
    return  lhs.weight < rhs.weight;
}
int main() {
    int n ;
    while (scanf("%d", &n) != EOF) {
        if ( n == 0 ) {
            break;
        }
        father.clear(); //每次重新开始后father哈希表的数据要清空需重新初始化!
        int total = 0; //每次结束后要重新赋值！
        int CountEdgeNum = 0;//每次结束后要重新赋值！
        vector<Edge> edge;
        for ( int i = 0 ; i < n - 1 ;
                i++) { //注意int和char类型的输入要用空格隔开！
            char u;
            int k;
            scanf(" %c %d", &u, &k); //首个顶点及道路数
            if ( k > 0) {
                for (int j = 0  ; j < k ; j++) {
                    char v;
                    int cost;
                    scanf(" %c %d", &v, &cost);
                    Edge e(u, v, cost); //保存边结点
                    edge.push_back(e); //存入动态数组
                }
            } else {
                continue;
            }
        }
        //按权值(费用)排序边表数组
        sort(edge.begin(), edge.end(), compare);
        for (int i = 0 ; i < edge.size() ; i++) { //遍历整个边表数组
            //取出每个结点的编号
            char u = edge[i].u;
            char v = edge[i].v;
            int cost = edge[i].weight;
            if (FindDisjointSet(u) != FindDisjointSet(v)) { //不在一个集合
                UnionDisjointSet(u, v); //按最小生成树的克鲁斯卡尔算法合并
                CountEdgeNum++; //边数+1
                total += cost; //费用累加
                if ( CountEdgeNum == n -
                        1) { //提前结束循环，当满足树的条件时边数 = 顶点数-1
                    break;
                }
            }
        }
        printf("%d\n", total);
    }
    return 0;
}