173 Count

[ditzone]

Aici puteţi discuta despre problema Count.

[•cristy]

zice-ti pls ceva teste mai naspa, sa vad de ce iau numa 20 de pct, mai am o sursa de 40 de pct, pe back, da pt toate testele pe care le-am dat, mi-au iesit, help...

[•filipb]

Incearca de exemplu asa:

Cod:

9 14
1 2
1 3
1 5
2 4
2 5
3 4
3 5
4 5
6 7
6 8
6 9
7 8
7 9
8 9

Trebuie sa dea (4, 1). Iar daca iti da, pune M in loc de 14, 16 si adauga muchiile (3,6) si (4,7). Tot (4,1) trebuie sa iti dea.
Ai grija cand graful nu e conex. Eu am testat destul de putin si am reusit sa iau max. Testele nu pot fi chiar asa de naspa pentru ca e greu sa construiesti un graf planar cu 30000 noduri.

[•cristy]

hmm...imi iese pentru ambele teste, ms pentru ele, am facut un alg simplu, am retinut toti vecinii intr-o lista de vecini, nu se poate sa fie mai mult de 6 vecini, ceea ce inseama ca o matrice de 30000*6 incape, luam fiecare nod A si cautam cu 2 parcurgeri, 2 noduri B si C printre vecinii lui, astfel incat B si C sa fie legate intre ele, evident B <> C, daca gaseam, mai cautam un nod D, tot intre vecinii lui A, care sa aiba leg cu B si C si tot asa, imi iese din timp pentru ultimele 2 teste, dar am gasit optimizari, ca sa intre in timp....

intre timp, am facut 70 de pct, pe ultimele imi da WA...

[•gogu]

Cred ca de la asta ti se trage.
Pot fi si noduri cu n-1 vecini dar cel putin unul din ei are gradul mai mic ca 6. Un graf in care legi nodul 1 de restul nodurilor e tot planar.
Trebuie sa retii cu liste de vecini de dimensiuni variabile.

[•cristy]

ms...o sa incerc...ms oricum...

[•filipb]

Da, de la asta este. Cel putin un nod are gradul < 6, nu toate. Toti arborii sunt planari si intr-un arbore pot exista noduri cu grade oricat de mari, dar intotdeauna vor fi frunzele cu grad 1 ( < 6 ). Incearca cu liste pentru fiecare nod (alocate dinamic).
Iar "dfs"-ul pe care il faci seamana cu cel de la c.conexe. Iei un nod NOD cu grad < 6, il analizezi, il marchezi ca folosit si decrementezi gradele vecinilor, daca un vecin are grad < 6 pornesti dfsu din el avand grija sa nu mai iei in considerare nodurile marcate ca folosite in numareare clicilor si tot asa. Iar cand ai iesit din dfs, continui lista de la NOD+1 incolo, vezi care e nefolosit inca si are grad < 6, etc...

[•danalex97]

In afara de prorietatile enumerate in articolul cu solutii , grafurile planare mai au vreo proprietate notabila ?

    Orice graf planar contine un nod cu grad mai mic decat 6
    Numarul maxim de muchii pe care il poate avea un graf planar este 3 * N - 6, unde N este numarul de noduri. Asadar O(M)=O(N) (M fiind numarul de muchii).
    Grafurile planare nu contin clici (subgrafuri complete) cu mai mult de 4 noduri (nu se poate desena in plan o clica de 5 noduri fara a intersecta muchiile acesteia).

Eventual vreun articol despre grafuri planare ?  Multumesc anticipat

[•wefgef]

Poti afla toate detaliile importante despre grafuri planare de pe Wikipedia.

[•danalex97]

10x.