031 Componente biconexe

[•pauldb]

Aici puteti discuta despre problema Componente biconexe din Arhiva educationala.

[•anna_bozianu]

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?

[•pauldb]

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

Cod:

5 6
1 2
2 3
1 3
3 4
4 5
3 5

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

Cod:

2
1 2 3
3 4 5

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.

[•anna_bozianu]

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    .

[•pauldb]

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

[•anna_bozianu]

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

[•MciprianM]

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

[•pauldb]

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.

[•Mishu91]

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)?

[•wefgef]

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.

[•Mishu91]

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

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

[•pauldb]

Nu cred ca ai inteles ce vrea sa spuna wefgef.

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.

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.

[•Mishu91]

10x Paul.
Am inteles acu

[•sima_cotizo]

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

[•mlazari]

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? 

[•wefgef]

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

[•S7012MY]

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

[•Mishu91]

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

[•S7012MY]

kbs-ul il iau si daca stiva e de 999

[•gorgovan]

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.

[•a_h1926]

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.

[•scipianus]

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 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]  
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  

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
Deci imi poate da cineva o idee cum afisez eficient si corect nodurile componentei biconexe stiind muchiile?  

[•savim]

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] ! ).

[•scipianus]

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? 

[•savim]

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.