031 Componente biconexe

[•scipianus]

Poti sa incerci ideea cu sortarea, nu cred ca sunt sanse sa iei tle, si eviti sa te complici.

Ca sa nu astepti sa ma uit pe sursa, iti dau link catre sursa mea, e destul de intuitiv scrisa, si poti sa compari cu ce ai facut tu:  http://infoarena.ro/job_detail/553869?action=view-source.

Gata,am luat 100pct facand sortarea (http://infoarena.ro/job_detail/597208). Mersi de ajutor 

[•yonatan]

Cred ca s-ar putea sa mai fie nevoie de niste tipuri de teste.
De exemplu sursa http://infoarena.ro/job_detail/601818?action=view-source  ia 100 de puncte desi este gresita linia 62: low[ x]=min(low[ x],low[ y]);. Corect: low[ x]=min(low[ x],def [y]);

Pe testul

Cod:

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

sursa gresita afiseaza

Cod:

1
1 2 3 4 5 6 7 8 

in loc de

Cod:

2
2 6 7 8 
1 2 3 4 5 

.

[•superman_01]

O alta probleme in care se poate aplica ideea de componente biconexe este problema Pamant , de la ONI 2011,clasele 11-12. 

[•AlexandruValeanu]

Am si eu o intrebare: care este algoritmul care determina numarul minim de muchii ce trebuie adaugate la un graf( si ce muchii ) pentru a deveni biconex?

[•wefgef]

Problema asta a fost propusa la CEOI 2000: http://ceoi.inf.elte.hu/probarch/00/p2.htm

[•AlexandruValeanu]

Multumesc de raspuns, se mai gasesc testele/solutii de la CEOI 2000 pe undeva ca pe site-ul Universitatii Babes-Bolyai nu mai exista nimic?

[•CosminRusu]

Buna!
Se poate adapta acest algoritm pentru a afla perechile de doua muchii, care eliminate din graf ar duce la pierderea conexitatii lui?
Singura solutie la care m-am gandit are complexitatea O(M * (N + M) ). Sunt curios daca exista o rezolvare mai buna privind complexitatea .

L.E: Curios nu a fost chiar cuvantul potrivit ) !

[•klamathix]

Mai asteptati cateva zile daca vreti sa raspundeti la asta  .

[•CosminRusu]

S-a terminat concursul . E cineva care a rezolvat-o sau care o stie rezolva ?

[•CostinV]

Am si eu o intrebare... de ce iau "Componente biconexa: numar gresit" pe primele 3 teste? Am luat testele si cand le rulez imi afiseaza exact ca acolo.
 

[•andreiulian]

Nu inteleg de ce iau numai 70 de puncte daca adaug la stiva si muchiile de intoarcere. Ma poate ajuta cineva?
http://www.infoarena.ro/job_detail/1335311?action=view-source
 

[•alexandru70]

O muchie critica nu e cumva muchia care uneste nodurile unei componente biconexe cu 2 noduri?

[•klamathix]

Așa este, scrie și pe topic-ul ăsta dacă te uiți mai în spate.

[•Theodor1000]

Cred ca ar trebui sa mai fie adaugate teste deoarece cu http://www.infoarena.ro/job_detail/1756040?action=view-source am luat 100, dar pica pe testul:
7 8
1 2
2 3
3 4
4 1
3 5
5 6
6 7
7 3

[•sulzandrei]

De ce a fost micsorata limita de memorie?

[•Andrei-27]

set ocupa mult mai multa memorie decat vector iar testul 8
departajeaza si in functie de asta .un exemplu de sursa "https://www.infoarena.ro/job_detail/2354194" care foloseste set.