OJ_还是畅通工程

题干

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


//并查集的应用：判断图的连通性

int set[10001];
//i下标是集合数据编号,set[i]是i的父亲的编号
//若i是根，可令set[i] = i
void InitDisjointSet(int n) {
    for(int i = 0; i<n; ++i) {
        set[i] = i;
    }
}

int FindDisjointSet(int u) {
    if(u == set[u]) {
        return u;
    } else {
        set[u] = FindDisjointSet(set[u]);//压缩路径
        return set[u];
    }
}

int UnionDisjointSet(int u,int v) {
    int uRoot = FindDisjointSet(u);
    int vRoot = FindDisjointSet(v);
    //把v并到u上
    set[vRoot] = uRoot;
}

struct Edge{
    int u;
    int v;
    int weight;
    //构造函数
    Edge(int _u,int _v,int _weight){
        u = _u;
        v = _v;
        weight = _weight;
    }
};

bool compare(Edge lhs,Edge rhs){
    return lhs.weight < rhs.weight;
}

int main()
{
    int n;
    while(scanf("%d",&n) != EOF){
        if(n == 0){
            break;
        }
        vector<Edge> edgeVec;
        InitDisjointSet(n+1);
        for(int i = 0; i<(n-1)*n/2; ++i){
            int u,v,weight;
            scanf("%d%d%d",&u,&v,&weight);
            Edge e(u,v,weight);
            edgeVec.push_back(e);
        }

        //Kruskal:1.排序，2.遍历edgeVec，加入子图
        sort(edgeVec.begin(),edgeVec.end(),compare);

        int totalWeight = 0;
        int curEdgeNum = 0;
        for(int i = 0;i< edgeVec.size();++i){
            int u = edgeVec[i].u;
            int v = edgeVec[i].v;
            int weight = edgeVec[i].weight;
            if(FindDisjointSet(u) != FindDisjointSet(v)){
                UnionDisjointSet(u,v);
                ++curEdgeNum;
                totalWeight += weight;

                if(curEdgeNum == n-1){
                    break;
                }
            }
        }
        printf("%d\n",totalWeight);
    }
    return 0;
}