Baobab
Problem
Viene fornito un grafico non orientato e non ponderato. Devi determinare se si tratta di un albero.
Input: La prima riga contiene un numero naturale N (N ≤ 100) - il numero di vertici nel grafico. Successivamente, in N righe, N numeri ciascuno - la matrice di adiacenza del grafico: nella riga i-esima, la j-esima posizione è 1 se i vertici i e j sono collegati da un bordo e 0 se non c'è bordo tra loro. Ci sono zeri sulla diagonale principale della matrice. La matrice è simmetrica rispetto alla diagonale principale.
Output: Stampa "YES" se il grafico è un albero e "NO" altrimenti.
Esempi
# |
Input |
Uscita |
1 |
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
|
NO |
2 |
3
0 1 0
1 0 1
0 1 0
|
SÌ |