Conteggio delle sorgenti (Editoriale)

Per risolvere il problema è conveniente passare dalla lista di adiacenza alla matrice di adiacenza del grafo.

Costruiamo una matrice di adiacenza di dimensione n \times n, dove l'elemento a_{ij} = 1, se esiste un arco orientato dal vertice $i$ al vertice $j$, e $0$ in caso contrario.

Poi, per ogni vertice $j$, contiamo il numero di archi entranti in esso. Questo si può fare sommando gli elementi della $j$-esima colonna della matrice di adiacenza.

Un vertice è una sorgente se e solo se non entra in esso alcun arco, cioè la somma degli elementi della colonna corrispondente è uguale a $0$.

Così, la risposta è il numero di vertici per i quali il numero di archi entranti è uguale a zero.

Esempio

Il grafo contiene una sorgente — il vertice $4$, poiché in esso non entra alcun arco.

Implementazione dell'algoritmo

Dichiariamo la matrice di adiacenza e l'array $in$, dove $in[i]$ memorizza il numero di archi entranti nel vertice $i$.

#define MAX 101
int g[MAX][MAX], in[MAX];

Leggiamo i dati in ingresso. In base alla lista di adiacenza data, costruiamo la matrice di adiacenza.

scanf("%d", &n);
for (i = 1; i <= n; i++)
{

Per ogni vertice $i$ leggiamo prima il numero di archi $k$ uscenti da esso.

  scanf("%d", &k);
  for (j = 0; j < k; j++)
  {

Per ogni arco $(i,x)$ impostiamo g[i][x] = 1.

    scanf("%d", &x);
    g[i][x] = 1;
  }
}

Scorriamo tutte le coppie di vertici del grafo. Per ogni arco $(i,j)$ incrementiamo il valore di $in[j]$ di $1$, poiché l'arco $(i,j)$ entra nel vertice $j$.

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
  if (g[i][j] == 1) in[j]++;

Contiamo il numero di vertici-sorgente — cioè i vertici in cui non entra alcun arco (per i quali in[i] = 0).

int source = 0;
for (i = 1; i <= n; i++)
  if (in[i] == 0) source++;

Stampiamo la risposta.

printf("%d\n", source);