Kruskal 模板

• 时间复杂度 O(ElogE)

int Kruskal(int n, int m){  
    int nEdge = 0, res = 0;  
    //将边按照权值从小到大排序  
    qsort(a, n, sizeof(a[0]), cmp);  
    for(int i = 0; i < n && nEdge != m - 1; i++){  
        //判断当前这条边的两个端点是否属于同一棵树  
        if(find(a[i].a) != find(a[i].b)){  
            unite(a[i].a, a[i].b);  
            res += a[i].price;  
            nEdge++;  
        }  
    }  
    //如果加入边的数量小于m - 1,则表明该无向图不连通,等价于不存在最小生成树  
    if(nEdge < m-1) res = -1;  
    return res;  
}