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