// Kruskal's MST using union-find trees #include #include int numVertices,numEdges; int *parent,*weight,numTrees; struct edge { int tail,head,weight; }; typedef struct edge edgeType; edgeType *edgeTab; int find(int x) // Find root of tree containing x { int i,j,root; // Find root for (i=x; parent[i]!=i; i=parent[i]) ; root=i; // path compression - make all nodes on path // point directly at the root for (i=x; parent[i]!=i; j=parent[i],parent[i]=root,i=j) ; return root; } void unionFunc(int i,int j) // i and j must be roots! { if (weight[i]>weight[j]) { parent[j]=i; weight[i]+=weight[j]; } else { parent[i]=j; weight[j]+=weight[i]; } numTrees--; } int weightAscending(const void* xin, const void* yin) // Used in call to qsort() { edgeType *x,*y; x=(edgeType*) xin; y=(edgeType*) yin; return x->weight - y->weight; } int main() { int i,MSTweight=0; int root1,root2; scanf("%d %d",&numVertices,&numEdges); edgeTab=(edgeType*) malloc(numEdges*sizeof(edgeType)); parent=(int*) malloc(numVertices*sizeof(int)); weight=(int*) malloc(numVertices*sizeof(int)); if (!edgeTab || !parent || !weight) { printf("error 2\n"); exit(0); } for (i=0;i