#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <stdbool.h>


int * get_vertices(FILE * fp);

int ** get_ribs(FILE * fp);

bool is_in_array(int * array, int element, int size);

int size_v = 0; // size of all vertices

int * vertices; // array of vertices

int ** ribs; // matrix array representing ribs of graph

struct rib
{
    int from;
    int to;
    int weight;
};


int main(int argc, char const *argv[])
{
    FILE * fp;

    get_vertices(fp);

    get_ribs(fp);

    int * used_vertices = (int*)malloc(size_v * sizeof(int));

    int used_size = 1;

    struct rib *skeleton = malloc((size_v - 1) * sizeof(struct rib));
    int skeleton_size = 0;

    used_vertices[0] = vertices[0];
    int k=0;
    int ok;
    struct rib *incidental;
    while (k<1000) {
        incidental = NULL; 
        ok = 0;
        int incidental_index = 0;

        /* Get all incidental ribs to used vertices */
        for (int i = 0; i < used_size; ++i)
        {
            for (int j = 0; j < size_v; ++j)
            {
                if (ribs[i][j] != 0 && ! is_in_array(used_vertices, j+1, size_v))
                {
                    // printf("%i-%i -> %i\n", i + 1, j+1, ribs[i][j]);
                    incidental = (struct rib*)realloc(incidental, 1 * sizeof(struct rib));
                    incidental[incidental_index].from = i+1;
                    incidental[incidental_index].to = j+1;
                    incidental[incidental_index].weight = ribs[i][j];
                    incidental_index++;
                    ok = 1;
                }
            }
        }

        /* Get min from all previous getted ribs */
        struct rib min = incidental[0];
        for (int i = 0; i < incidental_index; ++i)
        {
            if (incidental[i].weight < min.weight)
            {
                min = incidental[i];
            }

        }

        /* Adding min to used and skeleton */
        used_vertices[used_size] = min.to;
        used_size ++;
        skeleton[skeleton_size] = min;
        skeleton_size++;

        if (used_size == size_v)
        {
            printf("breked! OK\n");
            break;
        }
        k++;
    }

    for (int i = 0; i < skeleton_size; ++i)
    {
        printf("%i-%i -> %i\n", skeleton[i].from, skeleton[i].to, skeleton[i].weight);
    }


    printf("--------------------\n");
    for (int i = 0; i < size_v; ++i)
    {
        printf("%i\n", vertices[i]);
    }
    printf("     --------\n");
    for (int i = 0; i < size_v; i++)
    {
        for (int j = 0; j < size_v; j++)
        {
            printf("%i ", ribs[i][j]);
        }
        printf("\n");
    }
    printf("--------------------\n");
}


int * get_vertices(FILE * fp){
    int tmp;

    fp = fopen("vina.in", "r");
    while (fscanf(fp, "%i\n", &tmp) == 1){
        size_v ++;
    }
    fclose(fp);

    vertices = (int*)malloc(size_v * sizeof(int));

    fp = fopen("vina.in", "r");
    int i = 0;
    while (fscanf(fp, "%i\n", &vertices[i]) == 1){
        i ++;
    }
    fclose(fp);
    return vertices;
}


int ** get_ribs(FILE * fp)
{
    int from;
    int to;
    int weight;

    // Allocating memory for array
    ribs = (int**)malloc(size_v * sizeof(int));

    // Allocating memory for array items
    for (int i = 0; i < size_v; i++){
        ribs[i] = (int*)malloc(size_v * sizeof(int));
        for (int j = 0; j < size_v; ++j)
        {
            ribs[i][j] = 0; // Defaul value is 0 if another is not provided
        }
    }

    fp = fopen("ribs.in", "r");
    while (fscanf(fp, "%i-%i,%i\n", &from, &to, &weight) == 3){
        ribs[from-1][to-1] = weight;
        ribs[to-1][from-1] = weight;
    }
    fclose(fp);
}

bool is_in_array(int * array, int element, int size)
{
    for (int i = 0; i < size; ++i)
    {
        if (array[i] == element)
            return true;
    }
    return false;
}

#include "stdio.h"
#include "malloc.h"


struct rib
{
    int from;
    int to;
    int weight;
};

int main(int argc, char const *argv[])
{
    struct rib *incidental;

    for (int i = 0; i < 12; ++i)
    {
        incidental = NULL;
        for (int j = 0; j < 3; ++j)
        {
            printf("ok %i\n", j);
            incidental = (struct rib*)realloc(incidental, sizeof(struct rib));
            incidental[j].from = j+1;
            incidental[j].to = (j+1)*2;
            incidental[j].weight = (j+1)*4;
        }

        for (int k = 0; k < 3; ++k)
        {
            printf(" %i-%i=%i\n", incidental[k].from, incidental[k].to, incidental[k].weight);
        }
    }


}