Baobab
Problem
Es wurde ein nicht orientierter, nicht gewichteter Graph angegeben. Es muss festgestellt werden, ob es sich um einen Baum handelt.
Eingabe: Die erste Zeile enthält eine natürliche Zahl N (N ≤ 100) - die Anzahl der Scheitelpunkte im Diagramm. Weiter in N Zeilen nach N Zahlen - die Adjazenzmatrix des Graphen: In der i-ten Zeile an der j-Stelle steht 1, wenn die Scheitelpunkte i und j durch eine Kante verbunden sind, und 0, wenn keine Kante dazwischen liegt. Auf der Hauptdiagonale der Matrix stehen Nullen. Die Matrix ist symmetrisch relativ zur Hauptdiagonale.
Ausgabe: Ausgabe von "YES", wenn der Graph ein Baum ist, und "NO" andernfalls.
Beispiele
| № |
Eingabe |
Ausgabe |
| 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
|
YES |