#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<int> plusPetitArc(int **valAdj, int nbSommets, int nbArcs) {
    vector<int> arc(3, -1);
    int min;

    for(int i = 0; i < nbSommets; i++) {
        for(int j = 0; j < nbSommets; j++) {
            if(valAdj[i][j] != -1 && arc[0] == -1) {
                min = valAdj[i][j];
                arc[0] = i;
                arc[1] = j;
                arc[2] = min;
            }
            else if(valAdj[i][j] < min && valAdj[i][j] > -1) {
                min = valAdj[i][j];
                arc[0] = i;
                arc[1] = j;
                arc[2] = min;
            }
        }
    }

    cout << "Arete ajoutee : " << arc[0] << "  |   " << arc[1] << "  |   Valeur = " << arc[2] << endl;

    return arc;

}

bool sommetTrouve(vector<int> newSommets, int sommet) {
    for(int i = 0; i < newSommets.size(); i++) {
        if(newSommets[i] == sommet)
            return true;
    }
    return false;
}

int main()
{
    int **valAdj;
    int nbSommets; // Nombre de sommets du graphe
    int nbArcs; // Nombre d’arcs du graphe
    int sommetDepart; // Arcs du graphe
    int sommetArrivee;
    int valeurArc;
    int *tabTmp;
    vector< vector<int> > newArcs;
    vector<int> tmpArc;
    vector<int> newSommets;
    int newPoids = 0;



    /**
     * Lecture du fichier et création des différents tableaux
     **/

    ifstream sourceGraphe("graphe.txt");

    sourceGraphe >> nbSommets ;
    cout << "Nombre de sommets : " << nbSommets << endl;

    sourceGraphe >> nbArcs ;
    cout << "Nombre d'aretes : " << nbArcs << endl << endl ;
    cout << "Aretes du graphe:\n";

    valAdj = new int* [nbSommets];
    tabTmp = new int [nbSommets];

    for (int i = 0; i < nbSommets; i++)
        valAdj[i] = new int[ nbSommets ];

    for (int i = 0; i < nbSommets; i++)
        tabTmp[i] = -1;

    for(int i = 0; i < nbSommets; i++)
    {
        for(int j = 0; j < nbSommets; j++)
            valAdj[i][j] = -1; // -1 peut correspondre à l'infini
    }

    // On crée notre tableau adj avec les informations sur les arcs
    sourceGraphe >> sommetDepart ;
    while ( sommetDepart != -1 ) {
        sourceGraphe >> sommetArrivee ;
        sourceGraphe >> valeurArc ;
        valAdj[sommetDepart][sommetArrivee] = valeurArc;
        sourceGraphe >> sommetDepart ;
    };

    cout << endl;

    for(int i = 0; i < nbSommets; i++)
    {
        for(int j = 0; j < nbSommets; j++)
            cout << valAdj[i][j] << "\t";
        cout << endl;
    }
    cout << endl;



    /**
     * On gère le 1er sommet
     **/

    while (newSommets.size() != nbSommets) {
        cout << "---------------------" << endl;
        tmpArc = plusPetitArc(valAdj, nbSommets, nbArcs);
        newArcs.push_back(tmpArc);
        valAdj[tmpArc[0]][tmpArc[1]] = -1;
        valAdj[tmpArc[1]][tmpArc[0]] = -1;
        if(!sommetTrouve(newSommets, tmpArc[0]))
            newSommets.push_back(tmpArc[0]);
        if(!sommetTrouve(newSommets, tmpArc[1]))
            newSommets.push_back(tmpArc[1]);

        /* for(int i = 0; i < nbSommets; i++)
        {
            for(int j = 0; j < nbSommets; j++)
                cout << valAdj[i][j] << "\t";
            cout << endl;
        } */
        cout << endl;
        cout << "Nombre de sommets relies : " << newSommets.size() << endl << endl;

    }
    cout << "---------------------" << endl;
    cout << endl;
    cout << "Nouveaux sommets : " << endl;
    for(int i = 0; i < newSommets.size(); i++)
        cout << newSommets[i] << "   ";

    cout << endl << endl;
    cout << endl << "--------------------------------" << endl;
    cout << "Nouvelles aretes : " << endl << endl;
    cout << "Sommet" << "\t" << "Sommet" << "\t" << "Poids" << endl;
    for(int i = 0; i < newArcs.size(); i++) {
        newPoids += newArcs[i][2];
        cout << "  " << newArcs[i][0] << "\t" << "  " << newArcs[i][1] << "\t" << "  " << newArcs[i][2] << endl;
    }
    cout << endl << "Poids de l'arbre couvrant : " << newPoids << endl;

    return 0;
}