077 Tom & Jerry

[•domino]

Aici puteţi discuta despre problema Tom & Jerry.

[VladS]

Se poate face ceva cu cicluri ?
Eu ma gandeam la ceva de genu: Daca graful are un ciclu cu cel putin 4 noduri sau nu e conex afiseaza "NU". Altfel afiseaza "DA".
Partea nasoala e ca a mers doar pe testul din enunt  iar eu nu gasesc nici un contraexemplu.

[•greco]

Dupa cum spuneam... o problema trebuie rezolvata constructiv in loc sa iei diverse idei de rezolvare si sa le cauti contraexemple. In orice caz, e greu de scos, cauta dismantlable graphs pe google.

[VladS]

Am gasit cateva documente despre dismantlable graphs numai ca in ele nu prea se face referire la verificarea daca un graf este dismantible. Singurul algoritm care l-am gasit:

Cat timp graful are mai mult de un nod
1) Cauta doua noduri i si j astfel incat N(i) inclus in N(j)
2) Daca s-a gasit o astfel de pereche elimina nodul i din graf si continua
            altfel graful nu este dismantible

Daca a ramas un nod graful e dismantible

Am implementat numai ca nu prea merge (WA la greu). Algoritmul e bun sau am eu greseli de implementare ?

[•filipb]

Eu ma gandeam la ceva de genu: Daca graful are un ciclu cu cel putin 4 noduri sau nu e conex afiseaza "NU". Altfel afiseaza "DA".
Partea nasoala e ca a mers doar pe testul din enunt iar eu nu gasesc nici un contraexemplu.

Un contraexemplu nu e chiar greu de gasit:

Cod:

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

Tom se plaseaza in 1, Jerry neaparat in 4. Tom vine in 5 si oriunde muta Jerry el pierde ( si in graf exista si un ciclu de 5, si un ciclu de 4 ). Pentru a nu avea TOM strategie, ma gandeam ca ar trebui sa existe un ciclu in care fiecare nod sa nu apartina unui alt ciclu de lungime 3...
Si altceva: ma gandeam sa construiesc ceva cu toate starile posibile ( sa avem un arbore curent de solutii si sa "expandam" cazurile ulterioare din fiecare nod ). Cred k ar trebui sa ma uit si eu pe Google k nu prea mi-a iesit implementarea ( desi nu pare ceva deosebit... )