最小生成树Kruskal算法与并查集及其优化

#include<bits/stdc++.h> using namespace std; struct Road{ int from; int to; int weight; bool operator <(Road b) const{ return weight<b.weight; } }; int arr[1001]; Road arr2[10001]; /*并查集非递归优化*/ int findRoot(int val){ int tmp=val; while(arr[val]>0){ val=arr[val]; } while(arr[tmp]>0){ int temp=arr[tmp]; arr[tmp]=val; tmp=temp; } return val; } int main(){ long long num; long long val,temp1,temp2; while(scanf("%lld",&num)!=EOF&&num!=0){ memset(arr,-1,sizeof(arr)); //for(int i=0;i<1001;i++) cout<<arr[i]<<' '; int size=num*(num-1)/2; for(int i=0;i<size;i++){ scanf("%lld%lld%lld",&temp1,&temp2,&val); arr2[i].from=temp1; arr2[i].to=temp2; arr2[i].weight=val; } sort(arr2,arr2+size); //for(int i=0;i<size;i++) cout<<arr2[i].from<<' '<<arr2[i].to<<' '<<arr2[i].weight<<endl; int res=0; for(int i=0;i<size;i++){ temp1=findRoot(arr2[i].from); temp2=findRoot(arr2[i].to); if(temp1!=temp2) { arr[temp1]=temp2; res+=arr2[i].weight; } } printf("%d\n",res); } return 0; }

1070