arbciclu

Arbore de cicluri

== include(page="template/taskheader" task_id="arbciclu") ==

==Include(page="template/taskheader" task_id="arbciclu")==

Poveste ...

Un arbore de cicluri este un graf neorientat care are una din urmatoarele proprietati:

h2. Cerinta

* este un ciclu de lungime $K$ ({$K ≥ 3$})
* este un graf obtinut prin atasarea unui ciclu $C$ de lungime $K$ ({$K ≥ 3$}) la o muchie dintr-un arbore de cicluri $CT$

...
 
h2. Restrictii
 
...

Atasarea unui ciclu la o muchie dintr-un graf inseamna inlocuirea unei muchii din ciclu cu o muchie din graf (si de asemenea inlocuirea celor doua noduri ale muchiei din ciclu cu cele doua noduri ale muchiei din graf).
!problema/arbciclu?arbciclu.jpg!  
Dandu-se mai multe grafuri sa se determine pentru fiecare daca este un arbore de cicluri.

h2. Date de intrare

...

Prima linie a fisierului de intrare $arbciclu.in$ contine un numar natural $T$, reprezentand numarul de grafuri care se dau. Pentru fiecare graf dat, prima linie va contine doua numere naturale: $N$ si $M$. $N$ este numarul de noduri din graf si $M$ este numarul de muchii. Urmatoarele $M$ linii vor contine cate doua numere intregi $A$ si $B$, cu semnificatia ca exista o muchie intre nodul $A$ si nodul $B$. Nodurile din graf sunt numerotate cu numere de la $1$ la $N$.

h2. Date de iesire

...

Pentru fiecare graf, in ordinea data in fisierul de intrare, se va afisa in fisierul $arbciclu.out$ sirul $YES$ daca graful este un arbore de cicluri, sau $NO$ in caz contrar.
 
h2. Restrictii
 
* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 200.000$

h2. Exemplu

| arbciclu.in | arbciclu.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. arbciclu.in |_. arbciclu.out |
|2
3 3
1 2
1 3
3 2
4 5
1 2
1 3
3 2
4 3
2 4
| YES
YES |

== include(page="template/taskfooter" task_id="arbciclu") ==

==Include(page="template/taskfooter" task_id="arbciclu")==
 
 

1323