infoarena

Aici puteti discuta despre problema Dans (http://infoarena.ro/problema/dans).

Testele contin grafuri care au un ciclu eulerian?

Salut, m-am chinuit cu problema asta ceva mai mult timp  ](*,) si am ajuns la concluzia ca ori eu nu inteleg bine ceva ori enuntul e gresit. In enunt scrie foarte frumos :  

"De asemenea, din motive de eficienţă, în momentul finzalizării unui dans, în ring trebuie să >> rămână un singur dansator << din perechea curentă şi >> să urce doar un singur alt dansator << (cei doi dansatori fiind bineînţeles compatibili). În plus, acelaşi dansator poate dansa maxim două dansuri consecutive (evident, trei dansuri ar fi epuizante)."


 Eu de aici inteleg ca practic e un lant euler / ciclu euler adica ceva conex  :yahoo: . Poate gresesc ... ( astept pareri  #-o ).
Am o sursa demonstrativa :
http://www.infoarena.ro/job_detail/1219698 aici verific conexitatea si iau 0
http://www.infoarena.ro/job_detail/1219699 aici nu o verific si iau 100

Partea a doua suna asa: Bun sa zicem ca problema e facuta sa fie asa mai multe cicluri / lanturi ... dar atunci de ce sunt doar 2 noduri cu grad impar ??? de ce nu 4 6 8 ... 200 si sa scot 2 .. 3 .. 4 .. 100 lanturi  si de ce nu si vreo 3-4 cicluri ? Si totusi pentru 100 merge sa scot: doar un ciclu sau un lant, dar mai exista si varianta in care scot un ciclu dar mai sunt alte N cicluri care nu au legatura cu cel scos ( cicluri pe care nu le scot ) sau un lant si mai exista alte cicluri care nu au legatura cu lantul scos ( pe care iar nu le scot ) :banana: ? Dubios... ( zic eu ).

Nu știu cum sunt făcute testele, dar nu e corect să verifici dacă e conex în sensul clasic. Dacă ai o componentă conexă și un nod izolat e perfect ok dacă componenta are soluție. Ca să răspunzi NU trebuie să existe cel puțin două componente conexe care conțin muchii.

Mersi de raspuns, uite am incercat sa fac verificarea asa cum m-ai sfatuit.

1) am marcat care noduri apar sa aiba muchii ( deci nu sunt izolate )
2) am facut un DFS din noduri care NU sunt izolate
3) am verificat daca un nod nu apartie componentei conexe respective si NU este un nod izolat

Rezultatul este tot 0 puncte:

http://www.infoarena.ro/job_detail/1219706?action=view-source

Astept raspuns  :-'

Ok, am investigat putin. Exista intr-adevar teste cu noduri izolate, dar nu exista teste cu 2 componente care contin muchii. Motivul pentru care tu iei 0 in continuare e fiindca nu resetezi used-ul tot timpul si apare-ul deloc. Le-am initializat cu 0 la inceputul testului si am luat 100 cu sursa la care mi-ai dat link.

Ma poate ajuta si pe mine cineva? Pur si simplu nu stiu ce gresesc    :horsy:  Am facut ciclu eulerian dintr-un nod cu grad impar si afisam NU daca aveam mai mult de 2 noduri cu grad impar sau doar un singur nod cu grad impar...
http://www.infoarena.ro/job_detail/1240520?action=view-source