Gli esercizi

Testi e soluzioni di alcuni esercizi

Sorgenti e pozzi di un grafo

/*
**  pozzi_sorgenti.c
**
**  Letto in input un grafo orientato G=(V,E), rappresentarlo
**  mediante liste di adiacenza. Stampare tutti i vertici
**  sorgente e tutti i vertici pozzo.
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Febbraio 1999
*/


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

#define MAX 100

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


/*
**  leggi_lista
**
**  legge in input una sequenza di numeri interi fino a quando
**  l'utente non digita "-1". I numeri letti vengono man mano
**  memorizzati in una lista. La funzione restituisce il puntatore
**  al primo elemento della lista.
*/

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

  primo = NULL;
  scanf("%d", &a);
  while (a != -1) {
    p = malloc(sizeof(struct nodo));
    p->info = a;
    p->next = primo;
    primo = p;
    scanf("%d", &a);
  }
  return(primo);
}


/*
**  leggi_grafo
**
**  Per ogni vertice del grafo ne legge la lista di adiacenza.
**  Restituisce il numero di vertici di G (n=|V|).
*/

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

  printf("Numero di vertici: ");
  scanf("%d", &n);

  for (i=0; i<n; i++) {
    printf("%d: ", i);
    *(l+i) = leggi_lista();
  }

  return(n);
}


/*
**  calcola_grado
**
**  per ogni vertice v di G scorre le liste di adiacenza
**  di G per calcolare il grado di ogni vertice: crea
**  dinamicamente una matrice di due colonne ed n righe;
**  per ogni vertice memorizza nella prima colonna il numero
**  di spigoli uscenti e nella seconda il numero di spigoli
**  entranti. Restituisce il puntatore alla matrice.
*/

int *calcola_grado(struct nodo **l, int n) {
  int *m, i;
  struct nodo *p;

  /*
  **  alloco dinamicamente una matrice m di n*2 interi
  */

  m = malloc(sizeof(int)*2*n);
  if (m == NULL) {
    printf("Errore: memoria insufficiente.\n");
    exit(-1);
  }

  /*
  **  azzero la matrice
  */

  for (i=0; i<n; i++) {
    *(m+i*2+0) = 0;
    *(m+i*2+1) = 0;
  }

  /*
  **  scorro le liste di adiacenza di ogni vertice di G
  **  ed eseguo il calcolo.
  */

  for (i=0; i<n; i++) {
    p = *(l+i);
    while (p != NULL) {

      /*
      **  incremento il numero di spigoli uscenti da i
      */

      *(m+i*2) += 1;

      /*
      **  p->info e' adiacente ad i: incremento il numero
      **  di spigoli entranti in p->info.
      */

      *(m + (p->info)*2 + 1) += 1;

      p = p->next;
    }
  }

  return(m);
}


/*
**  pozzi_e_sorgenti
**
**  scorro la matrice m (nx2) creata dalla funzione
**  calcola_grado e stampo i vertici sorgente e quelli
**  pozzo.
*/

void pozzi_e_sorgenti(int *m, int n) {
  int i;

  printf("Sorgenti di G: ");
  for (i=0; i<n; i++) {
    if (*(m+2*i+1) == 0) {
      printf("%d ", i);
    }
  }

  printf("\nPozzi di G: ");
  for (i=0; i<n; i++) {
    if (*(m+2*i) == 0) {
      printf("%d ", i);
    }
  }
  printf("\n");
  return;
}


/*
**  main
**
**  funzione principale che richiama tutte le altre.
*/

int main(void) {
  struct nodo *liste[MAX];
  int n, *matrice;

  n = leggi_grafo(&liste[0]);
  matrice = calcola_grado(&liste[0], n);
  pozzi_e_sorgenti(matrice, n);

  return(0);
}