/* 2(b). W.A.P. to find a Minimum cost spanning tree of a given connected undirected graph using Kruskal's method. */

#include<stdio.h>
#include<conio.h>
int p[10],n=0,cost[10][10],minval,u,v;
// if p[x]=y then there is a path from y to x
void heap(int cost[10][10],int n)
{
    int i,j,min=99;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if ((cost[i][j] != 99) && (cost[i][j] < min))
                {
                    min = cost[i][j];
                    u = i;
                    v = j;
                }
            minval = min;
}
void Union(int u,int v,int n)
{
    int i;
    // If selected vertex v & any i are not connected to a common vertex
    for (i = 1; i <= n; i++)
    if (p[i] == p[v] && i != v)
        p[i] = p[u];
    p[v] = p[u];
}
void kruskal(int n,int cost[][10])
{
    int count = 0,i,j,t[20][2],mincost = 0;
    heap(cost,n);
    for (i = 1; i <= n; i++)
    p[i] = i; // None of the vertex connnected
    while (count < n-1)
    {
        cost[u][v] = cost[v][u] = 99;
        i = p[u];
        j = p[v];
        if (i != j)
        {
            count++;
            t[count][1] = u;
            t[count][2] = v;
            mincost += minval;
            Union(u,v,n);
        }
        heap(cost,n);
    }
    if (count != n-1)
        printf("NO spanning tree\n");
    else
    {
        printf("Spanning tree:\n");
        for (i = 1; i < n; i++)
            printf("< %d , %d>\n",t[i][1],t[i][2]);
        printf("\nMinimum Cost is = %d",mincost);
    }
}
void main()
{
    int n,cost[10][10],i,j;
    clrscr();
    printf("Enter the no. of nodes : ");
    scanf("%d",&n);
    printf("\nEnter the elements\n");
    for (i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            {
                scanf("%d",&cost[i][j]);
                if (i == j)
                    cost[i][i] = 0;
                else
                {
                    if (cost[i][j] == 0)
                        cost[i][j] = 99;    
                }
            }
        kruskal(n,cost);
        getch();
}
/* OUTPUT
Enter the no. of nodes : 3
Enter the elements :
2 0 5
4 0 3
0 5 4
Spannig tree is :
< 2 , 3 >
< 2 , 1 >

Minimum cost is = 7
*/