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

typedef struct _cvor_liste
{
   int broj; /* indeks suseda */
   struct _cvor_liste* sledeci;
} cvor_liste;

#define MAX_BROJ_CVOROVA 100
cvor_liste* graf[MAX_BROJ_CVOROVA]; /* Graf predstavlja niz pokazivaca na pocetke listi suseda */

/* Ubacivanje na pocetak liste */
cvor_liste* ubaci_u_listu (cvor_liste* lista, int broj)
{
  cvor_liste* novi=malloc (sizeof(cvor_liste));
  if (novi == NULL){
    fprintf (stderr, "Neuspela alokacija.\n");
    exit (EXIT_FAILURE);
  }
  novi->broj=broj;
  novi->sledeci=lista;
  return novi;
}

void obrisi_listu(cvor_liste* lista)
{
  if (lista)
  {
    obrisi_listu(lista->sledeci);
    free(lista);
  }
}

void ispisi_listu(cvor_liste* lista)
{
  if (lista) { printf("%d ",lista->broj);
  ispisi_listu(lista->sledeci); }
}


/* Rekurzivna implementacija DFS algoritma */
void DFS(int i, int posecen[])
{
  cvor_liste* sused;
  printf("Posecujem cvor %d\n",i);
  posecen[i]=1;

  for(sused=graf[i]; sused!=NULL; sused=sused->sledeci)
    if (!posecen[sused->broj])
      DFS(sused->broj, posecen);
}

int main()
{
  int i, j, br_suseda, sused, broj_cvorova;
  int posecen[MAX_BROJ_CVOROVA];

  printf ("Unesi broj cvorova grafa : ");
  scanf("%d",&broj_cvorova);

  for (i=0; i<broj_cvorova; i++)
    posecen[i] = 0;

  for (i=0; i<broj_cvorova; i++)
  {
    graf[i]=NULL;
    printf ("Koliko cvor %d ima suseda : ",i);
    scanf("%d",&br_suseda);

    for (j=0; j<br_suseda; j++)
    {
      do
      {
        printf ("Unesi broj %d. suseda cvora %d : ",j+1,i);
        scanf("%d",&sused);
      }
      while (sused<0 || sused>=broj_cvorova); // u petlji je dok se ne unese ispravan sused

      graf[i]=ubaci_u_listu (graf[i],sused);
    }
  }
  printf ("\n");
  for (i=0; i<broj_cvorova; i++)
  {
    printf("%d - ",i);
    ispisi_listu(graf[i]);
    printf("\n");
  }
  DFS(0, posecen);
  return 0;
}