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

#define N_MAX 105

int matrice[N_MAX][N_MAX];
int contor = 0;
int nodes[N_MAX];
int vizitat[N_MAX]; // se intializeaza automat cu 0, nodurile fiind initial nevizitate
int lista[N_MAX];
int culoare[N_MAX];
int timp_init[N_MAX];
int timp_final[N_MAX];
int timp;
int sp[N_MAX];
int cost[N_MAX];
int nr_arce;
int nr_noduri;
int parinte[N_MAX];
int noduriParcurse;


void initializare()
{
    int i, j;
    for (i = 0; i < N_MAX; i++)
    {
        for (j = 0; j < N_MAX; j++)
        {
            matrice[i][j] = 0;
        }
    }
}

void introducere_nod(int i)
{
    nodes[contor++] = i;
    nr_noduri++;
}

void DFS(int nodStart) // DFS
{
    printf("%d ", nodStart);
    vizitat[nodStart] = 1; // initializam primul nod, pe care l si introducem de la tastatura ca fiind vizitat;
    for (int i = 0; i < N_MAX; i++)
    {
        if (matrice[nodStart][i] && !vizitat[i])
        {
            DFS(i);
        }
    }
}
/*//vector culoare
//vector sp-structura precedenta;
//timp_init  si timp_final[x] - memoram momentul in care e colorat in negru*/

void CautareInAdancime(int nod)
{
    culoare[nod] = -1; // -1 adica gri
    timp++;
    timp_init[nod] = timp;
    for (int i = 0; i < N_MAX; i++)
    {
        if (matrice[nod][i] && culoare[i] == 0)
        {
            sp[i] = nod;
            CautareInAdancime(i);
        }
    }
    culoare[nod] = 1; /* se seteaza culoarea pe negru */
    timp++;
    timp_final[nod] = timp;
}
void TraversareInAdancime()
{
    for (int i = 0; i < N_MAX; i++)
    {
        culoare[i] = 0; /* 0 - alb */
        sp[i] = 0;
    }
    timp = 0;
    for (int i = 0; i < N_MAX; i++)
    {
        if (!culoare[i])
            CautareInAdancime(i);
    }
}
/* -1 = gri / 0 = alb / 1 = negru */


void introducere_arc(int i, int j, int cost)
{
    int index, ai, aj;
    for (index = 0; index < contor; index++)
    {
        if (nodes[index] == i)
            ai = index;
    }
    for (index = 0; index < contor; index++)
    {
        if (nodes[index] == j)
            aj = index;
    }

    matrice[ai][aj] = cost;
    matrice[aj][ai] = cost;
}

void stergere_arc(int i, int j)
{
    int index, ai, aj;
    for (index = 0; index < N_MAX; index++)
    {
        if (nodes[index] == i)
            ai = index;
    }
    for (index = 0; index < N_MAX; index++)
    {
        if (nodes[index] == j)
            aj = index;
    }
    matrice[ai][aj] = 0;
    matrice[aj][ai] = 0;
}

void init_parcurgere()
{
    for (int i = 0; i < contor; ++i) {
        vizitat[i] = 0;
    }
}

void afisare_matrice()
{
    int i, j;
    for (i = 0; i < contor; i++)
    {
        for (j = 0; j < contor; j++)
        {
            printf("%d ", matrice[i][j]);
        }
        printf("\n");
    }
    printf("\n");

}

void suprima_nod(int i) {
    int a, b, x;
    for (a = 0; a < contor; a++) {
        if (nodes[a] == i) {
            x = a;
        }
    }
    for (a = x; a <= contor - 1; a++) {
        nodes[a] = nodes[a + 1];
    }

    for (a = x; a <= contor; a++) {
        for (b = 0; b < contor; b++) {
            matrice[a][b] = matrice[a + 1][b];
        }
    }
    for (b = x; b <= contor; b++) {
        for (a = 0; a < contor; a++) {
            matrice[a][b] = matrice[a][b + 1];

        }
    }
    contor--;

}

void prim(int nod)
{
    int pondere = INT_MAX,i,j, pondere_totala = 0, urm;
    vizitat[nod] = 1;
    noduriParcurse++;
    for(i = 0; i<N_MAX; i++)
        if(matrice[nod][i] < pondere)
        {
            pondere = matrice[nod][i];
            urm = i;
        }
    pondere_totala += pondere;
    vizitat[urm] = 1;
    noduriParcurse++;

    printf("%d %d",nod, urm);
    printf("%d =>",nod);

    while(noduriParcurse < contor)
    {
        pondere = INT_MAX;

        for(i=0;i<N_MAX;i++)
            for(j=0;j<N_MAX;j++)
                if((matrice[i][j] != 0) && (vizitat[i] == 1) && (vizitat[j] == 0))
                {
                    if(matrice[i][j] < pondere)
                    {
                        pondere = matrice[i][j];
                        urm = j;
                    }
                }

        if(pondere < INT_MAX)
            pondere_totala += pondere;

        vizitat[urm] = 1;
        noduriParcurse++;

        if(noduriParcurse < contor)
            printf(" %d -> ", urm);
        else printf(" %d",urm);
    }
}

int main()
{
    int costt;
    int opt;
    int a, b, c, nodInceput, nodStart;
    while (1)
    {
        printf("1.Initializare noduri cu 0\n");
        printf("2.Introducere nod\n");
        printf("3.Introducere arc\n");
        printf("4.Stergere nod\n");
        printf("5.stergere arc\n");
        printf("6.Afisare matrice adiacenta\n");
        printf("7.Exit\n");
        printf("8.Parcurgere in adancime basic\n");
        printf("9.Parcurgere in adancime CLR\n");
        printf("10.Algoritmul lui Prim\n");
        printf("\nIntroduceti opt:");
        scanf("%d", &opt);
        switch (opt)
        {
            case 1:
                initializare();
                break;
            case 2:
                scanf("%d", &a);
                introducere_nod(a);
                break;
            case 3:
                printf("Introduceti prim nod: \n");
                scanf("%d", &b);
                printf("Introduceti cel de-al doilea nod: \n");
                scanf("%d", &c);
                printf("Introduceti cost: ");
                scanf("%d", &costt);
                introducere_arc(b, c, costt);
                break;
            case 4:
                scanf("%d", &a);
                suprima_nod(a);
                break;
            case 5:
                scanf("%d", &b);
                scanf("%d", &c);
                stergere_arc(b, c);
                break;
            case 6:
                afisare_matrice();
                break;
            case 7:
                exit(0);
                break;
            case 8:
                printf("Introduceti nodul de la care doriti sa incepeti: \n");
                scanf("%d", &nodInceput);
                DFS(nodInceput);
                printf("\n");
                break;
            case 9:
                printf("\n");
                TraversareInAdancime();
                break;
            case 10:
                printf("Introduceti nodul de start: ");
                scanf("%d",&nodStart);
                prim(nodStart);
                break;
            default:
                printf("Ati introdus optiunea gresita\n");
                break;

        }
    }
    return 0;
}