289 Arbore de cicluri

[ditzone]

Aici puteţi discuta despre problema Arbore de cicluri.

[•MarcvsHdr]

Totusi, am o nelamurire in legatura cu solutia oficiala. Fie urmatorul set de date de intrare:

1
5 6
1 2
1 3
1 4
2 5
3 5
4 5

Conform ideii de rezolvare descrisa acolo... acest graf ar trebui sa fie un arbore de cicluri, dar din enuntul problemei eu inteleg ca nu este (pentru ca doua cicluri trebuie sa aiba in comun o singura muchie si doua noduri, iar in cazul de fata e vorba de 2 muchii si 3 noduri). 

I'm confused, solutia ar trebui sa dea YES sau NO? 

[•S7012MY]

Ce optimizari trebuie facute pt a lua 100 p? Eu am implementat idea din articol dar nu iau mai mult de 80p

Cred ca ar putea fi marita limita de timp putin

[•dushmi]

Rog pe cineva care are o sursa de 100 mai veche sa o trimita din nou. Eu iau 60 de puncte cu solutia buna si ma gandesc sa nu fie de la noile limite .

[•freak93]

Am testat sursa lui Gavrila Vlad. Se pare ca el inca ia 100. Deocamdata pare buna limita incercati sa mai optimizati.

[•GavrilaVlad]

Eu am luat 100 abia dupa ce am parsat citirea. (e drept, am trecut de la 90 la 100, de la 60 s-ar putea sa trebuiasca sa mai optimizezi).

[•dushmi]

Merci pentru raspunsuri. Ati avut dreptate Limita de timp este ok

[•visanr]

Cred ca e prea mica limita de timp. Am o solutie in O(T * N * log M) care ia 60.  

[•lucian666]

Salut . La problema aceasta iau doar 0 pct cu 5 incorrect si restul TLE.
Procedez astfel:
1.Pt fiecare nod de gradul 2 il bag intr-o coada.
2.Pt fiecare element din coada,ii iau cei doi vecini (i,j) si le scad gradul cu o unitate,elimin vf curent din coada din graf,iar apoi adaug muchiile(i,j),(j,i) .
3.Daca la finalul algoritmului am doar 2 noduri ramase inseamna ca am solutie ...

Este buna ideea de rezolvare ,sau am uitat eu ceva   ?

Mentionez ca pt retinerea grafului neorientat folosesc un set.

Multumesc Anticipat !!!

Later Edit.Am mai modificat cate ceva prin program si am reusit sa iau 20 pct,cu 3 incorect si restul tle  

Cat va da pt urmatorul test ?

Cod:

4
3 3
1 2
1 3
3 2
4 5
1 2
1 3
3 2
4 3
2 4
5 6
1 2
1 3
1 4
2 5
3 5
4 5
4 6
1 2
1 3
1 4
2 3
2 4
3 4

mie imi da :

Cod:

YES
YES
YES
NO

Multumesc anticipat!!!

Later Edit 2 .Am reusit sa iau 50 pct,pe restul testelor am TLE.

Cred ca e prea mica limita de timp. Am o solutie in O(T * N * log M) care ia 60. 

Am reusit sa scot si eu aceeasi complexitate ...Cred ca ar trebui marita putin limita de timp 

[•freak93]

Voi mari limita de timp. Scuze ca a durat atat.

[•vladrochian]

Testul acesta este valid?

Cod:

1
5 6
1 2
1 3
1 4
5 2
5 3
5 4

Cu doua surse diferite de 100 de puncte primesc raspunsuri diferite