/* Programik pokazuje jak dziala algorytm wyznaczania drzewa rozpinajacego grafu metoda
   przeszukiwania w glab. Dane wejsciowe przedstawione sa za pomoca list incydencji.
   Plik 'in.txt', ktory przechowuje dane wejsciowe wyglada nastepujaco (przyklad):
   ------------------- in.txt --------------------------
           4
           2 3 4
           1 3 4
           1 2 4
           1 2 3
   -----------------------------------------------------
           
    - w pierwszej linii podana jest liczba wierzcholkow grafu.
    -  W kolejnych n liniach umieszczone sa listy incydencji dla kazdego
       z n wierzchokow.
       
    Dane wyjsciowe sa wypisywane na ekranie i przedstawiaja opis krawedzi utworzonego
    drzewa rozpinajacego (tj. pary wierzcholkow).
    
    Literatura: W.Lipski "Kombinatoryka dla programistow"  */

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

struct wierzcholek
{
    int x;
    struct wierzcholek *nast;
};

typedef struct wierzcholek wierzcholek;


/* Tworzenie list incydencji dla kazdego z wierzcholkow */
void stworz_liste(wierzcholek **lista, int y)
{
    wierzcholek *e, *tmp;
    
    e = malloc(sizeof(wierzcholek));
    e->x = y;
    e->nast = NULL;
    
    if(*lista == NULL) *lista = e;
    else
    {
       tmp = *lista;
       while(tmp->nast)
           tmp = tmp->nast;
         
           tmp->nast = e;
    }
}


/* Znajdowanie drzewa rozpinajacego grafu spojnego metoda przeszukiwania w glab */
/*     v - Od ktorego wierzcholka zaczynamy,
       nowy - tablica logiczna z wierzcholkami. Bedzie przyjmowac wartosci 0 i 1,
       tab - tablica z listami incydencji.
*/
void wgd(int v, int *nowy, wierzcholek **tab)
{
     nowy[v] = 0;
     
     while(tab[v])
     {
         if( nowy[ tab[v]->x ])
         {
              printf("%d %d\n",v,tab[v]->x);
              wgd(tab[v]->x,nowy,tab);
         }              
                  
         tab[v] = tab[v]->nast;         
     }
}


/* Czyszczenie pamieci */
void wyczysc(wierzcholek **tab, int liczba_w)
{
     wierzcholek *e;
     int i;
     
     for(i=1;i<=liczba_w;i++)
         while(tab[i])
           {
               e = tab[i]->nast;
               free(tab[i]);
               tab[i] = e;
           }                  
}  


int main()
{
    FILE *fp_in;         /* Uchwyt pliku wejsciowego */
    wierzcholek **tab;   /* Tablica ze wskaznikami na listy incydencji */
    int liczba_w;        /* Liczba wierzcholkow w grafie */
    int i,y;             /* Zmienne pomocnicze */
    char znak;           /* Bedziemy sprawdzac, czy ten znak nie jest koncem wiersza w pliku */ 
    
    
    
    /* Czytamy informacje z pliku */
    fp_in = fopen("in.txt","r");
    if(!fp_in) exit(1);
    
    fscanf(fp_in, "%d", &liczba_w);    /* Pobranie liczby wierzcholkow */
    
    tab = malloc(liczba_w*sizeof(wierzcholek*));   /* Alokacja tablicy ze wskaznikami na listy incydencji */
    for(i=0;i<=liczba_w;i++) tab[i] = NULL;
    i = 1;
        
    while(fscanf(fp_in, "%d", &y) != EOF)
    {
        stworz_liste(&tab[i], y);
        
        znak = fgetc(fp_in);
        if(znak=='\n') i++;
        
    }
    fclose(fp_in);
    
    
    /* Deklaracje oraz wywolanie wlasciwej procedury */
    int *nowy = malloc(liczba_w*sizeof(int));
    for(i=0; i<=liczba_w; i++) nowy[i] = 1;
    
    wgd(1, nowy, tab);
    
    free(nowy);
    wyczysc(tab,liczba_w);
    free(tab);
    
    getchar(); 
    return 0;
}