#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
#include <string.h>

int i,j,a,b,u,v,ne=1;
int min,mincost=0,parent[];
int find(int);
int uni(int,int);

int main()
{
    int anzahl;

    printf("Bitte geben Sie die Anzahl der Knoten ein\n");
    scanf("%d",&anzahl);

    typedef struct knoten
    {
        char name[15];
        int position;

    }KNOTEN;

    typedef struct kante
    {
        char knotenA[15];
        char knotenB[15];
        int pos_A;
        int pos_B;
        int cost;


    }KANTEN;


    KNOTEN knoten[anzahl];
    KANTEN kanten[anzahl];

    for(int i = 0;i<anzahl;i++)
    {

        printf("\nKnoten %d\n",i);
        printf("**********\n");
        printf("Geben Sie einen Namen ein(15 Zeichen): ");
        scanf("%s",&knoten[i].name);
        knoten[i].position = i;

    }

    printf("\nVorhandene Knoten:\n\n");
    for(int i = 0;i<anzahl;i++)
    {

        printf("%d. Name: %s \n",i,knoten[i].name);


    }

    printf("\n");
    int matrix[anzahl][anzahl];

    int pos_kanten = 0;

    for(int zeile = 0;zeile<anzahl;zeile++)
    {
        for(int spalte = 0;spalte<anzahl;spalte++)
        {

            if(spalte > zeile){

                char check;
                printf("\nKante/Strecke zwischen %s und %s vorhanden? (j/n):\n",knoten[zeile].name,knoten[spalte].name);
                scanf(" %c",&check);



                if(check == 'j' || check == 'J' || check == 'y'|| check == 'Y')
                {
                    printf("Bitte Abstand/Kosten eingeben fuer:  %s nach %s\n",knoten[zeile].name,knoten[spalte].name);
                    scanf("%d",&matrix[zeile][spalte]);

                    strcpy(kanten[pos_kanten].knotenA,knoten[zeile].name);
                    strcpy(kanten[pos_kanten].knotenB,knoten[spalte].name);
                    kanten[pos_kanten].pos_A = knoten[zeile].position;
                    kanten[pos_kanten].pos_B = knoten[spalte].position;
                    kanten[pos_kanten].cost = matrix[zeile][spalte];
                    pos_kanten = pos_kanten + 1;

                }
                else
                {
                        matrix[zeile][spalte] = 0;
                }


            }
            if(spalte == zeile)
            {
                matrix[zeile][spalte] = 0;
            }

        }

    }

    int sort_stellen = ((anzahl*anzahl)-anzahl)/2;
    int sort[sort_stellen];
    int sort_pos = 0;

    for(int zeile = 0;zeile<anzahl;zeile++)
    {
        for(int spalte = 0;spalte<anzahl;spalte++)
        {

            if(spalte < zeile)
            {
                matrix[zeile][spalte] = matrix[spalte][zeile];

            }
            if(spalte > zeile && matrix[zeile][spalte] != 0)
            {

                sort[sort_pos] = matrix[zeile][spalte];
                sort_pos = sort_pos +1;

            }

        }

    }


    //Ausgabe der Kanten

    printf("\nEingegebene Kanten: ");
    for(int i = 0; i < sort_pos;i++)
    {
        printf("%d ",sort[i]);
    }
    printf("\n");



   //Bubblesort :)
   for (int i = 1; i < sort_pos ; i++)
   {
      for (int j = 0; j < sort_pos - i ; j++)
      {
          if (kanten[j].cost > kanten[j+1].cost)
          {
              KANTEN temp = kanten[j];
              kanten[j] = kanten[j+1];
              kanten[j+1] = temp;
          }
      }
   }

//Ausgabe der Matrix
    printf("\n");
    printf("              ");
    for(int i = 0;i<anzahl;i++)
    {
        printf("%16s",knoten[i].name);
    }
    printf("\n");
    for(int i = 0;i<anzahl;i++)
    {
        printf("%15s",knoten[i].name);
        for(int j = 0;j<anzahl;j++)
        {

            printf("%15d ",matrix[i][j]);

        }
        printf("\n");
    }



//Tabelle

printf("\n Kanten:\n");
printf("\n            VON            NACH    Gewicht\n");
for(int i = 0; i < anzahl;i++)
{
    printf("%15s %15s %10d \n",kanten[i].knotenA,kanten[i].knotenB,kanten[i].cost);
}

printf("\n");

//Kruskal

printf("The edges of Minimum Cost Spanning Tree are\n");

for(int i = 0;i<anzahl;i++)
    {

        for(int j = 0;j<anzahl;j++)
        {

            if(matrix[i][j]==0)
            {
                matrix[i][j]=999;
            }

        }
        printf("\n");
    }

printf("\n");
    printf("              ");
    for(int i = 0;i<anzahl;i++)
    {
        printf("%16s",knoten[i].name);
    }
    printf("\n");
    for(int i = 0;i<anzahl;i++)
    {
        printf("%15s",knoten[i].name);
        for(int j = 0;j<anzahl;j++)
        {

            printf("%15d ",matrix[i][j]);

        }
        printf("\n");
    }

while(ne < anzahl)
{
    for(i=0,min=999;i<anzahl;i++)
    {
        for(j=0;j < anzahl;j++)
        {
            if(matrix[i][j] < min)
            {if (matrix[i][j] >0){
                min=matrix[i][j];
                a=u=i;
                b=v=j;
            }}
        }
    }
    u=find(u);
    v=find(v);
    if(uni(u,v))
    {
        printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
        mincost +=min;
    }
    matrix[a][b]=matrix[b][a]=999;
}
printf("\n\tMinimum cost = %d\n",mincost);


}

int find(int i)
{
    while(parent[i])
    i=parent[i];
    return i;
}

int uni(int i,int j)
{
    if(i!=j)
    {
        parent[j]=i;
        return 1;
    }
        return 0;
}