infoarena

Aici puteti discuta despre problema Componente biconexe (http://infoarena.ro/problema/biconex) din Arhiva educationala (http://infoarena.ro/arhiva-educationala).

As vrea sa intreb daca urmatorul algoritm determina corect componentele biconexe:

Pas 1. Se considera muchiile critice ca fiind componente biconexe si se elimina din graf.
Pas 2. Se elimina toate nodurile izolate ramase.
Pas 3. Toate componentele conexe ramase sunt celelalte componente biconexe ale grafului initial.

O a doua intrebare : Graful initial este conex?

1. Algoritmul oferit de tine nu e corect (daca l-am inteles bine). Uite un contraexemplu:

Tu vei spune ca exista o singura componenta biconexa formata din tot graful, in timp ce raspunsul corect este

2. In toate testele problemei, graful este conex. In cazul in care ar fi mai multe componente conexe, atunci ar trebui sa rulezi algoritmul prezentat pentru fiecare componenta.

Mai mult decat edificator exemplul. Faceam o confuzie grava. Mersi. Ce spuneam eu duce mai degraba (poate gresesc) renuntand la pasul 2 spre componente tare conexe. Cat despre conexitate grafului din problema ... am facut pana la urma rezolvarea la general   :) .

Nu, nu merge nici acolo. Componentele tare-conexe sunt pentru grafuri orientate, in timp ce componentele biconexe sunt pentru grafuri neorientate.

 :oops: iar am dat-o in bara. Totusi, pentru cultura mea generala, un graf neorientat fara muchii critice are vreo denumire.

E voie cu copy paste? Am vazut sursa "oficiala" la alti useri.
L.E. @PDB am inteles

E voie. Ideea surselor vizibile este de a invata de la altii si de a putea testa ce au facut altii imbunatatind programele voastre. Nu putem garanta ca toata lumea este bine intentionata, dar pentru cei interesati merita sa pastram acest avantaj.

As avea o intrebare, cam legata de componentele biconexe. Cum se poate determina daca o muchie este punte in graf(parca asa ii zice, adica daca o elimin nu mai pot ajunge dintr-o parte in alta a grafului)? :D

O muchie este critica <=> componenta sa biconexa nu contine alte muchii.

O modalitate de a determina muchiile critice este urmatoarea: faci un DF si pentru fiecare nod te uiti cat de sus poti ajunge mergand in subarborele sau si apoi pe o muchie de intoarcere. In momentul cand gasesti un nod care are un fiu din care nu poti ajunge mai sus decat nivelul tatalui, ai gasit muchia critica nod - fiu.

Pai daca e asa, cred ca cel mai simplu ar fi sa fac exact ca la componentele biconexe, iar cand am gasit o componenta biconexa numar cate elemente are, si daca are 2, e tzais :)

Nu cred ca ai inteles ce vrea sa spuna wefgef.


Algoritmul acesta este exact cel pentru determinarea punctelor de articulatie explicat in problema cu o mica modificare (un > in loc de  >=) . Se pot, deci, determina muchiile critice (sau puntile) fara a mai determina componentele biconexe.

10x Paul.
Am inteles acu :)

Pe testul 4 de exemplu primesc 4pct desi acasa iau segfault. Sa fie oare o eroare in grader cpp?

LE : mea culpa, aveam define special pentru sursele de acasa :)

Din indicatii se intelege ca radacina arborelui DFS este intotdeauna punct de articulatie, deoarece nu are stramosi, deci nu se poate ajunge in modul indicat la un stramos al sau.  ??? Ceea ce sigur ca nu e adevarat, deoarece radacina arborelui poate fi orice nod. Am inteles eu ceva gresit? Sau radacina e un caz aparte?  :-k

Rădăcina este nod critic dacă are cel puţin doi fii în parcurgerea DFS. Într-adevăr, este un caz aparte :).

Ma poate ajuta cineva sa corectez algoritmul asta http://infoarena.ro/job_detail/469196?action=view-source (http://infoarena.ro/job_detail/469196?action=view-source)
Am imlementat ca in cartea d-nei Cerchez dar se pare ca nu functioneaza. :-k

Tare mă îndoiesc că în cartea respectivă autorul și-a declarat o stivă de 10 miliarde de elemente. Tu iei KBS, nu incorect/TLE.

kbs-ul il iau si daca stiva e de 999

Salut!
Am cateva intrebari in legatura cu problema si cu sursa oficiala.

- in cartile mele de acasa( Pregatire pentru grupele de performanta, Volumul III al doamnei Cerchez si Introducere in Algoritmi de Udi Manber) cat si in articolul lui Mugurel Ionut Andreica am vazut ca se introducea o muchie in stiva indiferent daca era muchie de intoarcere sau nu, pe cand in sursa lui Marius Stroe se introduce numai cand nu este muchie de intoarcere..

Din ce motiv? Sau ce altceva mai este diferit la sursa lui Marius astfel incat algoritmul functioneaza?

- cum modific algoritmul lui Marius ca sa aflu muchiile?
Initial credeam ca din cauza ca nu se cer muchiile, Marius a renuntat la introducerea muchiei in stiva.
Insa dupa ce i-am modificat putin sursa am observat ca nu aceasta este cauza.

Ma poate ajuta cineva? Nu stiu ce gresesc la implementare, am respectat pasii din solutia de 100 de puncte si nu stiu ce poate fi. As aprecia daca s-ar uita cineva peste sursa mea sa-mi spuna ce gresesc.
http://infoarena.ro/job_detail/595289?action=view-source
Multumesc anticipat.

Am facut aceasta problema cu implementare de O(n+m) - liste de adiacenta alocate dinamic , dar ma incurca foarte tare modul in care trebuie afisate componentele biconexe (atunci cand le determin , in loc sa le afisez,trebuie sa le numar si sa le retin cumva undeva ca sa le afisez mai tarziu). Am incercat aici http://infoarena.ro/job_detail/596464 (http://infoarena.ro/job_detail/596464) sa retin componentele in liste alocate dinamic in felul urmator : cand extrag o muchie [x,y] a componentei biconexe din stiva , retin nodul x in lista ; daca la finalul determinarii acelei componente biconexe am retinut in lista componentei doar un nod , atunci il retin si pe y. Asta deoarece muchiile sunt retinute in modul [x1,x2] [x2,x3] .... [xn,x1]  :-k
Si totusi cum de mi se zice ca pe 8 teste am afisat gresit componentele?  ??? Inainte mai facusem o varianta in care retineam din muchia [x,y] si pe x si pe y,iar apoi la afisare pentru fiecare componenta reinitializam un vector bool "afisat" pentru a nu afisa de 2 ori acelasi nod,dar bineinteles ca din cauza reinitializarii la fiecare componenta se facea O(n^2) sau chiar mai mult si deci lua 70pct cu TLE pe ultimele 3 teste  #-o

Poate sa-mi explice cineva de ce gandirea mea de afisare din prima varianta ar fi gresita?  ???

LE : m-am mai uitat pe teste si am incercat sa mai repar la afisare cu diverse variabile prim,ultim,etc. si cu ceva verificari dar inca raman 6 teste cu afisarea incorecta  ](*,) http://infoarena.ro/job_detail/596484 (http://infoarena.ro/job_detail/596484)
Deci imi poate da cineva o idee cum afisez eficient si corect nodurile componentei biconexe stiind muchiile?  :-k

Din ce stiu, ar trebui sa-ti mearga prima idee de afisare, insa nu am avut timp sa ma uit pe sursa ta.

Mai simplu, daca stii muchiile unei componente, poti adauga nodurile fiecarei muchii (x,y) intr-un vector, sortezi vectorul, si afisezi doar elementele distincte.

Asta se poate realiza intr-un mod destul de simplu. (if A[ i ] != A[i - 1] afiseaza A[ i ], ai grija la A[0] ! ).

Pai da,s-ar putea si asa,adica fiecare nod ar aparea de 2 ori,dar sortarea nu ar mai mari complexitatea inutil?  ??? Cand ai sa ai timp poti sa te uiti pe sursa mea sa vezi totusi de ce nu ar fi bun?  :-k

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 (http://infoarena.ro/job_detail/553869?action=view-source).

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

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
sursa gresita afiseaza
in loc de
.

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

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?

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

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?

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 :)) !

Mai asteptati cateva zile daca vreti sa raspundeti la asta  :P.

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

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.
 

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
 ](*,)

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

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

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

De ce a fost micsorata limita de memorie?

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.