最小生成树 Kruska算法

Kruskal算法的过程： （1） 将全部边按照权值由小到大排序。 （2） 按顺序（边权由小到大的顺序）考虑每条边，只要这条边和我们已经选择的边不构成圈，就保留这条边，否则放弃这条边。 算法 成功选择(n-1)条边后，形成一个棵最小生成树，当然如果算法无法选择出(n-1)条边，则说明原图不连通。怎么判断是否已经构成圈了呢？用并查集来判断，是否构成圈。 输入 第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000) 第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000) 输出 输出最小生成树的所有边的权值之和。 输入示例 9 14 1 2 4 2 3 8 3 4 7 4 5 9 5 6 10 6 7 2 7 8 1 8 9 7 2 8 11 3 9 2 7 9 6 3 6 4 4 6 14 1 8 8 输出示例 37 #include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,m; int father[1005]; struct node{ int s; int e; int w; }a[50005]; int cmp(node x,node y){ return x.w<y.w; } int findfather(int x){ while(x!=father[x]) x=father[x]; return x; } int main(){ int i,sum,ans; while(scanf("%d%d",&n,&m)!=EOF){ sum=ans=0; for(i=0;i<=n;i++) father[i]=i; for(i=0;i<m;i++){ scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].w); } sort(a,a+m,cmp);//从小到大排序， for(i=0;i<m;i++){ if(ans<n){ if(findfather(a[i].s)!=findfather(a[i].e)){//判断是不是属于同一个圈 father[findfather(a[i].e)]=findfather(a[i].s);//将其变成同一个圈 sum+=a[i].w; ans++;//判断是否已经将n个点走完 } } } printf("%d\n",sum); } }