Ciclo hamiltoniano

/*
**  hamiltoniano.c
**
**  Leggere in input un grafo orientato G=(V,E) ed una sequenza
**  S di vertici di G. Verificare se S e' un ciclo hamiltoniano,
**  ossia un ciclo semplice in G che consente di raggiungere
**  tutti i vertici di G. Il grafo G deve essere rappresentato
**  utilizzando la struttura dati delle liste di adiacenza, la
**  sequenza S deve essere rappresentata mediante una lista.
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Settembre 2001
*/

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

#define MAX 50

struct nodo {
  int info;
  struct nodo *next;
};

struct nodo *leggi_lista(void) {
  struct nodo *p, *primo, *ultimo;
  int a, i, n;

  primo = NULL;
  ultimo = NULL;
  printf("Numero di elementi: ");
  scanf("%d", &n);
  for (i=0; i<n; i++) {
    scanf("%d", &a);
    p = malloc(sizeof(struct nodo));
    p->info = a;
    p->next = NULL;
    if (!primo)
      primo = p;
    if (ultimo)
      ultimo->next = p;
    ultimo = p;
  }
  return(primo);
}

int leggi_grafo(struct nodo *l[]) {
  int i, n;

  printf("Numero di vertici del grafo: ");
  scanf("%d", &n);
  for (i=0; i<n; i++) {
    printf("Lista di adiacenza del vertice %d\n", i);
    l[i] = leggi_lista();
  }
  return(n);
}

int adiacente(int u, int v, struct nodo *l[]) {
  struct nodo *p;

  p = l[u];
  while (p!=NULL && p->info != v)
    p = p->next;
  if (p == NULL)
    return(0);
  else
    return(1);
}

int hamiltoniano(struct nodo *primo, struct nodo *l[], int n) {
  int visitato[MAX], i, flag;
  struct nodo *p;

  for (i=0; i<n; i++)
    visitato[i] = 0;
  p = primo;
  visitato[p->info] = 1;
  while (p->next != NULL && !visitato[p->next->info] && adiacente(p->info, p->next->info, l)) {
    visitato[p->next->info] = 1;
    p = p->next;
  }
  flag = 1;
  for (i=0; i<n && flag==1; i++)
    flag = visitato[i];
  return(flag);
}

int main(void) {
  struct nodo *lista[MAX], *primo;
  int n;

  n = leggi_grafo(lista);
  primo = leggi_lista();
  if (hamiltoniano(primo, lista, n))
    printf("La sequenza di vertici e' un ciclo hamiltoniano in G.\n");
  else
    printf("La sequenza di vertici non e' un ciclo hamiltoniano.\n");
  return(1);
}