Són arbres? P45106


Statement
 

pdf   zip

html

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.

Public test cases
  • Input

    7
    1  3
    1  3
    1  5
    3  1 0 5
    1  5
    4  6 4 3 2
    1  5
    
    7
    2  1 2
    2  0 2
    2  0 1
    2  4 6
    2  3 5
    2  4 6
    2  3 5
    
    2
    0
    0
    

    Output

    es un arbre
    NO es un arbre
    NO es un arbre
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++