// gestione incrociata di matrice di adiacenza e liste di adiacenza di un grafo orientato
// tutte le operazioni hanno costo ottimo:
//   creazione arco: costo O(1)
//   rimozione arco: costo O(1)
//   verifica presenza arco: costo O(1)
//   elenco vertici adiacenti: costo O(k) dove k è il numero di archi uscenti dal nodo corrente

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

typedef struct list list;
struct list {
  int dest;
  list *prev, *next;
};

#define N 10

list* A[N][N]; //matrice di adiacenza

list* L[N]; //lista di adiacenza

void init()
{
  int i, j;
  for (i = 0; i < N; ++i) {
    L[i] = NULL;
    for (j = 0; j < N; ++j)
      A[i][j] = NULL;
  }
}

void connect(int i, int j)
{
  if (A[i][j] == NULL) {
    printf("Connetto %d e %d\n", i, j);
    list *new_node = malloc(sizeof(list));
    new_node->dest = j;
    new_node->prev = NULL;
    new_node->next = L[i];
    if (L[i] != NULL)
      L[i]->prev = new_node;
    L[i] = new_node;
    A[i][j] = L[i];
  }
}

void disconnect(int i, int j)
{
  if (A[i][j] != NULL) {
    printf("Disconnetto %d e %d\n", i, j);
    list *old_node = A[i][j];
    A[i][j] = NULL;
    if (old_node->prev == NULL)
      L[i] = old_node->next;
    else
      old_node->prev->next = old_node->next;
    if (old_node->next != NULL)
      old_node->next->prev = old_node->prev;
    free(old_node);
  }
}

void print_list(int i)
{
  printf("Lista di %d: ", i);
  list *p = L[i];
  while (p != NULL) {
    printf("%d ", p->dest);
    p = p->next;
  }
  printf("\n");
}

void print_query(int i, int j)
{
  printf("A[%d][%d] = %d\n", i, j, A[i][j] ? 1 : 0);  
}

int main()
{
  init();
  connect(0, 1);
  connect(0, 2);
  connect(1, 2);
  connect(2, 1);
  connect(3, 0);
  print_list(0);
  print_query(0, 3);
  print_query(3, 0);
  print_list(3);
  disconnect(3, 0);
  print_query(3, 0);
  print_list(3);
  connect(0, 3);
  connect(0, 4);
  connect(0, 5);
  print_list(0);
  disconnect(0, 3);
  print_list(0);
  disconnect(0, 1);
  print_list(0);
  disconnect(0, 5);
  print_list(0);
  return 0;
}