Numero di vertici pendenti 1 (Editoriale)

Per ogni vertice $i$ calcoliamo il numero di vertici a esso adiacenti. Se questo numero è uguale a $1$, allora il vertice $i$ è pendente.

Esempio

I grafi riportati negli esempi hanno il seguente aspetto:

Nel primo esempio il grafo contiene due vertici di grado $1$. Di conseguenza, in esso ci sono due vertici pendenti.

Nel secondo esempio non ci sono vertici di grado $1$ (pendenti).

Implementazione dell'algoritmo

Dichiariamo un array $m$, dove $m[i]$ — è il numero di vertici adiacenti al vertice $i$.

#define MAX 1010
int m[MAX];

Leggiamo la matrice di adiacenza del grafo non orientato. Per ogni arco $(i,j)$ incrementiamo di $1$ il valore di $m[i]$ (il valore di $m[j]$ verrà incrementato quando si considererà l'arco $(j,i)$).

scanf("%d",\&n);
memset(m,0,sizeof(m));
for (i = 0; i \< n; i++)
for (j = 0; j \< n; j++)
{
  scanf("%d",\&val);
  if (val) m[i]++;
}

Se m[i] = 1, allora il vertice $i$ è collegato esattamente a un vertice, cioè è pendente. Contiamo il numero di tali vertici e salviamo il risultato nella variabile $res$.

res = 0;
for (i = 0; i \< n; i++)
  if (m[i] == 1) res++;

Stampiamo la risposta.

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