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);
}