CHEI, RUNDA 2 .CAMPION 2010

[•dornescuvlad]

Salut!
Am o problema la implementarea solutiei oficiale si nu o inteleg partial.In solutie scrie ca se va alege primul purcelus nedeschis (cu cheie sau spart) adica nodul cu valoarea cea mai mica, care n-a fost "deschis".De aici incercam sa gasim un circuit, ca sa aflam porcusorul care trebuie deschis (spart, iar apoi facem un DFS sa deschidem ceilalti, cu cheile gasite in acesta).
Un ciclu intr-un graf neorientat este echivalent cu un circuit intr-un graf orientat ?
Voi alege nodul (porcusorul) cu gradul cel mai mare ? (Adica cu cele mai multe chei ? si voi deschide vecinii acestuia) Este cumva o abordare de tip greedy sau n-am inteles eu bine solutia deloc?

Multumesc.

[•auRSTAR]

Cu un DFS intr-un graf neorientat obtii 100 de puncte.

[•skull]

Trebuie doar sa determini numarul de componente conexe. Daca asociezi un graf problemei observi ca fiecare nod are gradul intern MAXIM 1 (doar un purcelus are cheia lui) deci nu exista posibilitatea ca la o parcurgere sa ramana un nod nevizitat din componenta conexa pe care o parcurgi. Sper ca te-am ajutat cat de cat, nu ma pricep sa dau explicatii . Ia-ti niste exemple si o sa observi cum functioneaza.

[•APOCALYPTO]

Se poate lua 100 si daca dublezi muchiile si determini componenetele conexe .
Dar trebuie neaparat sa parsezi citirea altfel vei lua 63.

[•S7012MY]

Eu cu citiri in c++ luam 63 si cu citiri in c luam 97 )

[•klamathix]

Merge si fara parsare daca faci cu disjoint data set si eviti dfs-ul. Probabil.

[•APOCALYPTO]

Merge intradevar cu multimi disjuncte fara parsare, dar tot trebuie sa foloseti citirea cu scanf().
Cu streamuri se ia 75.