Baobá
Problem
É fornecido um gráfico não direcionado e não ponderado. Você precisa determinar se é uma árvore.
Entrada: A primeira linha contém um número natural N (N ≤ 100) - o número de vértices no gráfico. Em seguida, em N linhas, N números cada - a matriz de adjacência do gráfico: na i-ésima linha, a j-ésima posição é 1 se os vértices i e j estiverem conectados por uma aresta e 0 se não houver aresta entre eles. Existem zeros na diagonal principal da matriz. A matriz é simétrica em relação à diagonal principal.
Saída: Imprima "SIM" se o gráfico for uma árvore e "NÃO" caso contrário.
Exemplos
| # |
Entrada |
Saída |
| 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
|
NÃO |
| 2 |
3
0 1 0
1 0 1
0 1 0
|
SIM |