Són arbres? P45106

Un graf és un conjunt de vèrtexos (també anomenats nodes) i un conjunt d’arestes entre els vèrtexos. Un arbre és un graf connex sense cicles. (Un arbre general no és més que un arbre per al qual s’ha fixat un node com a arrel, i on s’ha escollit una ordenació d’esquerra a dreta dels fills de cada node.)

(Per veure un exemple amb el primer graf de l’exemple d’entrada-sortida, consulteu la versió pdf o ps d’aquest enunciat.)

Feu un programa que decideixi si diversos grafs donats són arbres o no. Per comoditat, suposarem que els $n$ vèrtexos d’un graf estan numerats $0, 1, \dots, n - 1$.

Entrada

L’entrada consisteix en la descripció de diversos grafs. Cada graf comença amb el nombre de vèrtexos $n \ge 1$. Segueixen $n$ línies, cadascuna amb el nombre de veïns del vèrtex $i$-èsim seguit d’aquests veïns en qualsevol ordre. A tots els grafs, no hi ha arestes repetides ni arestes d’un vèrtex a ell mateix.

Sortida

Per a cada graf donat, escriviu una línia indicant si és un arbre o no.