|
Titlul: 173 Count Scris de: ditzone din Ianuarie 21, 2006, 17:07:00 Aici puteţi discuta despre problema Count (http://infoarena.ro/problema/count).
Titlul: 173 Count Scris de: Rus Cristian din Februarie 03, 2006, 18:05:43 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... ](*,)
Titlul: 173 Count Scris de: Filip Cristian Buruiana din Februarie 04, 2006, 09:54:01 Incearca de exemplu asa:
Cod: 9 14 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. Titlul: 173 Count Scris de: Rus Cristian din Februarie 04, 2006, 11:11:42 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... Titlul: 173 Count Scris de: Gogu Marian din Februarie 04, 2006, 11:22:01 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. Titlul: 173 Count Scris de: Rus Cristian din Februarie 04, 2006, 11:35:16 ms...o sa incerc...ms oricum...
Titlul: 173 Count Scris de: Filip Cristian Buruiana din Februarie 04, 2006, 12:47:41 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... Titlul: Răspuns: 173 Count Scris de: Dan H Alexandru din Septembrie 03, 2012, 15:10:45 In afara de prorietatile enumerate in articolul cu solutii , grafurile planare mai au vreo proprietate notabila ?
Citat 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 ? :ok: Multumesc anticipat Titlul: Răspuns: 173 Count Scris de: Andrei Grigorean din Septembrie 05, 2012, 12:48:22 Poti afla toate detaliile importante despre grafuri planare de pe Wikipedia (http://en.wikipedia.org/wiki/Planar_graph).
Titlul: Răspuns: 173 Count Scris de: Dan H Alexandru din Septembrie 05, 2012, 15:08:29 10x. :ok:
|