#include<stdio.h> 
#include<conio.h> 
int p,q,u,v,n; 
int min=99,mincost=0; 
int t[50][2],i,j; 
int parent[50],edge[50][50]; 
main() 
{ 
clrscr(); 
printf("\n Enter the number of nodes"); 
scanf("%d",&n); 
for(i=0;i<n;i++) 
{ 
printf("%c\t",65+i); 
parent[i]=-1; 
} 
printf("\n"); 
for(i=0;i<n;i++) 
{ 
printf("%c",65+i); 
for(j=0;j<n;j++) 
scanf("%d",&edge[i][j]); 
} 
for(i=0;i<n;i++) 
{ 
for(j=0;j<n;j++) 
if(edge[i][j]!=99) 
if(min>edge[i][j]) 
{ 
min=edge[i][j]; 
u=i; 
v=j; 
} 
p=find(u); 
q=find(v); 
if(p!=q) 
{ 
t[i][0]=u; 
t[i][1]=v; 
18 
 
mincost=mincost+edge[u][v]; 
sunion(p,q); 
} 
Else 
{ 
t[i][0]=-1;t[i][1]=-1; 
} 
min=99; 
} 
printf("Minimum cost is %d\n Minimum spanning tree is\n" ,mincost); 
for(i=0;i<n;i++) 
if(t[i][0]!=-1 && t[i][1]!=-1) 
{ 
printf("%c %c %d", 65+t[i][0],65+t[i][1],edge[t[i][0]][t[i][1]]);printf("\n"); 
} 
getch(); 
} 
sunion(int l,int m) 
{ 
parent[l]=m; 
} 
find(int l) 
{ 
if(parent[l]>0) 
i=parent[i]; 
return i; 
}

I2luY2x1ZGU8c3RkaW8uaD4gCiNpbmNsdWRlPGNvbmlvLmg+IAppbnQgcCxxLHUsdixuOyAKaW50IG1pbj05OSxtaW5jb3N0PTA7IAppbnQgdFs1MF1bMl0saSxqOyAKaW50IHBhcmVudFs1MF0sZWRnZVs1MF1bNTBdOyAKbWFpbigpIAp7IApjbHJzY3IoKTsgCnByaW50ZigiXG4gRW50ZXIgdGhlIG51bWJlciBvZiBub2RlcyIpOyAKc2NhbmYoIiVkIiwmbik7IApmb3IoaT0wO2k8bjtpKyspIAp7IApwcmludGYoIiVjXHQiLDY1K2kpOyAKcGFyZW50W2ldPS0xOyAKfSAKcHJpbnRmKCJcbiIpOyAKZm9yKGk9MDtpPG47aSsrKSAKeyAKcHJpbnRmKCIlYyIsNjUraSk7IApmb3Ioaj0wO2o8bjtqKyspIApzY2FuZigiJWQiLCZlZGdlW2ldW2pdKTsgCn0gCmZvcihpPTA7aTxuO2krKykgCnsgCmZvcihqPTA7ajxuO2orKykgCmlmKGVkZ2VbaV1bal0hPTk5KSAKaWYobWluPmVkZ2VbaV1bal0pIAp7IAptaW49ZWRnZVtpXVtqXTsgCnU9aTsgCnY9ajsgCn0gCnA9ZmluZCh1KTsgCnE9ZmluZCh2KTsgCmlmKHAhPXEpIAp7IAp0W2ldWzBdPXU7IAp0W2ldWzFdPXY7IAoxOCAKIAptaW5jb3N0PW1pbmNvc3QrZWRnZVt1XVt2XTsgCnN1bmlvbihwLHEpOyAKfSAKRWxzZSAKeyAKdFtpXVswXT0tMTt0W2ldWzFdPS0xOyAKfSAKbWluPTk5OyAKfSAKcHJpbnRmKCJNaW5pbXVtIGNvc3QgaXMgJWRcbiBNaW5pbXVtIHNwYW5uaW5nIHRyZWUgaXNcbiIgLG1pbmNvc3QpOyAKZm9yKGk9MDtpPG47aSsrKSAKaWYodFtpXVswXSE9LTEgJiYgdFtpXVsxXSE9LTEpIAp7IApwcmludGYoIiVjICVjICVkIiwgNjUrdFtpXVswXSw2NSt0W2ldWzFdLGVkZ2VbdFtpXVswXV1bdFtpXVsxXV0pO3ByaW50ZigiXG4iKTsgCn0gCmdldGNoKCk7IAp9IApzdW5pb24oaW50IGwsaW50IG0pIAp7IApwYXJlbnRbbF09bTsgCn0gCmZpbmQoaW50IGwpIAp7IAppZihwYXJlbnRbbF0+MCkgCmk9cGFyZW50W2ldOyAKcmV0dXJuIGk7IAp9