Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<stdlib.h>
- struct Edge{int u,v,w;};
- int p[100];
- int find(int i)
- {
- while(p[i]!=i)i=p[i];
- return i;
- }
- int cmp(const void *a,const void *b)
- {
- return((struct Edge*)a)->w-((struct Edge*)b)->w;
- }
- int main()
- {
- int V=4,E=5,count=0,total=0;
- struct Edge e[]={{0,1,10},{0,2,6},{0,3,5},{1,3,15},{2,3,4}};
- qsort(e,E,sizeof(e[0]),cmp);
- for(int i=0;i<V;i++)
- p[i]=i;
- printf("Eges in MST");
- for(int i=0;i<E && count<V-1;i++)
- {
- int root_u=find(e[i].u);
- int root_v=find(e[i].v);
- if(root_u!=root_v)
- {
- printf("%d-%d(%d)\n",e[i].u,e[i].v,e[i].w);
- total+=e[i].w;
- p[root_u]=root_v;
- count++;
- }
- }
- printf("total cost:%d",total);
- return 0;
- }
RAW Paste Data
Copied
