Baobab
Problem
Un graphique non orienté et non pondéré est donné. Vous devez déterminer s'il s'agit d'un arbre.
Entrée : La première ligne contient un nombre naturel N (N ≤ 100) - le nombre de sommets dans le graphe. Ensuite, dans N lignes, N numéros chacun - la matrice d'adjacence du graphe : dans la i-ème ligne, la j-ème position est 1 si les sommets i et j sont reliés par une arête, et 0 s'il n'y a pas d'arête entre eux. Il y a des zéros sur la diagonale principale de la matrice. La matrice est symétrique par rapport à la diagonale principale.
Sortie : Imprime "OUI" si le graphique est un arbre et "NON" sinon.
Exemples
| # |
Entrée |
Sortie |
| 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
NON |
| 2 |
3
0 1 0
1 0 1
0 1 0
OUI |