Fişierul intrare/ieşire: | itree.in, itree.out | Sursă | Happy Coding 2006 |
Autor | Mugurel Ionut Andreica | Adăugată de | |
Timp execuţie pe test | 0.35 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Itree
Fie o multime de intervale pe axa OX. Consideram ca doua intervale se intersecteaza daca si numai daca au mai mult de un punct in comun (de exemplu intervalele [1, 5] si [3, 10] se intersecteaza, dar [1, 2] si [2, 3] nu se intersecteaza). Graful asociat acestei multimi de intervale este graful in care se asociaza un nod fiecarui interval si o muchie intre nodurile corespunzatoare fiecarei perechi de intervale care se intersecteaza.
Un graf G se numeste graf de intervale daca exista cel putin o multime de intervale al caror graf asociat sa fie izomorf cu G.
Un arbore (graf orientat conex cu N varfuri si N - 1 muchii) se numeste arbore de intervale daca este in acelasi timp si graf de intervale.
Cerinta
Dandu-se un arbore, decideti daca acesta este arbore de intervale.
Date de Intrare
Fisierul itree.in va contine pe prima linie un intreg T reprezentand numarul de teste din fisier. In continuare sunt descrisi T arbori. Pentru fiecare arbore pe prima linie se va afla un numar N - numarul de noduri ale arborelui. Urmatoarele N - 1 linii contin cate o pereche de numere A B, cu semnificatia ca exista o muchie intre nodurile A si B.
Date de Iesire
Fisierul itree.out va contine pe T linii. Pentru fiecare arbore din fisierul de intrare se va afisa YES
daca acesta este arbore de intervale, respectiv NO
in caz contrar.
Restrictii
- 1 ≤ N ≤ 100.000
Exemplu
itree.in | itree.out |
---|---|
3 3 1 2 2 3 1 4 1 2 1 3 3 4 | YES YES YES |