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, …, n − 1.

Entrada

L’entrada consisteix en la descripció de diversos grafs. Cada graf comença amb el nombre de vèrtexos n ≥ 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.