022 Paduri de multimi disjuncte

[•filipb]

Aici puteti discuta despre problema Paduri de multimi disjuncte.

[•Mishu91]

Imi sugerati niste probleme la care se folosesc multimi disjuncte, pls

[•devilkind]

Voi adauga in enuntul problemei mai multe probleme,intre timp poti incerca curcubeu de pe infoarena si walls de pe sgu (e in primul volum parca)

[•Mishu91]

Mersi Tiberiu.

P. S.: Pentru cine e interesat, am mai gasit o problema care se rezolva cu multimi disjuncte, Bile

[•CezarMocan]

Ar mai fi Mexc, Jstc si problemele in care e nevoie de APM, de exemplu Desen.

[•devilkind]

Am adaugat in enuntul problemei la aplicatii mai multe probleme care folosesc multimi disjuncte.

[•stinky]

cred ca ar putea fi adaugata si problema 502 flori (de la oji 2006)

[•wefgef]

Testele la această problemă ar trebui refăcute. O sursă care nu foloseşte nici euristica reuniunii după rang nici pe cea a comprimării drumului obţine 100 de puncte.

[•xtreme]

"Asupra acestei abordari putem aplica insa 2 euristici care scad foarte mult timpul de executie:"
Ce inseamna "2 euristici" ??Vrei sa zici "2 metode euristice"?
Asta inseamna ca metoda prezentata da o solutie corecta intotdeauna da nu exista nicio demonstratie oficiala(sau stiuta)?(sau euristicul tau e legat de timpul de executie)
wiki :"In computer science, a heuristic algorithm, or simply a heuristic, is an algorithm that is able to produce an acceptable solution to a problem in many practical scenarios, in the fashion of a general heuristic, but for which there is no formal proof of its correctness."
Si ar trebui schimbat aici:
"Reuniunea dupa rang: Pentru fiecare multime tinem minte inaltimea arborelui care reprezinta acea multime si atunci cand vrem sa unim 2 arbori, il unim pe cel mai mic de cel mai mare."
De fapt uniunea a doi arbori nu depinde de nimic.Putem sa reunim oricum cat timp respecta AUB=C.
Dar probabil autorul vrea sa pastreze pentru fiecare multime limita superioara de rang(sau inaltime), fapt ce il zice mai incolo in enunt.Atunci nu ar fi trebuit scris "Reuniune dupa limitele superioare a rangurilor"?Dar la ce folosesti limitele superioare a ranguriilor?
Pe mine m-a indus in eroare modul "inprecis" in care a fost redactat acest subiect.Normal ca unii zic :-Ce ca se subintelege !, si considera abordarea mea o rea intentie desi nu e deloc asa, dar daca dintr-o propozitie ai de inteles 2 idee care se contrazic nu ai cum sa fii sigur ca cea pe care tu ai considerat-o cea mai probabil de a fii adevarata  e chiar cea adevarata in caz ca nu demonstrezi.

[•pauldb]

Problema aceasta prezinta multe lipsuri si va fi refacuta integral in viitorul apropiat.

[•wefgef]

@xtreme: Probabil ca autorul explicatiei a tradus-o din Cormen:

"By using two heuristics, however, we can achieve a running time that is almost linear in the total number of operations m"

[•devilkind]

Mda imi cer scuze pentru problemele aparuta la intelegerea solutiei. Am explicat pe limbajul meu si dupa felul in care am inteles eu din cormen. Intr-adevar am crezut ca se subintelege. O sa incerc sa rescriu zilele acestea solutia pe un limbaj mai clar. Inca odata imi cer scuze pentru neplacerile provocate.

[•xtreme]

Va multumesc pentru raspunsuri.Iar daca am parut nepoliticos va rog sa ma scuzati.

[•johsonsbabi]

salut, am cautat dar ce am gasit nu a fost pe intelesu meu
daca aveti timp spuneti-mi ce face codu asta, e din sursa oficiala, in special a doua linie... nu am mai intalnit ceva asemanator 

if (find(x) == find(y))   
{fprintf(stderr,"%d ", i);return 0;}


ty

[•Mishu91]

Chestia aia îl ajută pe autor la verificarea testelor, mai precis a condiției ca două elemente să nu fie din aceeași mulțime. Poți trece peste linia respectivă, întrucât nu are legătură cu rezolvarea efectivă a problemei.

[•Bit_Master]

Dar nu putem sa legam de tata nu doar la interogari, ci si la reuniuni (chiar daca radacina se schimba pe urma), ca scurteaza drumul? Oricand parcurgem sa gasim radacina?

Si oricum, iei 100 si fara prima euristica. Adica conteaza atat de mult? Pentru ca oricum cand legi direct de radacina
scurtezi f mult drumul si ce conteaza adancimea unei grupe din moment ce la la prima parcurgere o faci 1?

[•Anna_cristina]

Buna:)
Am trimis problema asta si nu reusesc sa iau mai mult de 40 de puncte..puteti sa-mi spuneti cum sa o fac mai eficient?

Cod:

#include<fstream>
#include<iostream>
using namespace std;

long v[100005],n,m;

int cauta(long x)
{while(v[x]!=x)
    x=v[x];
 return x;
} 

void reun(long x,long y)
{long xx,yy;
 xx=cauta(x);
 yy=cauta(y);
 v[yy]=xx;
}  

int main()
{long i,x,y;
 int cod;
 ifstream f("disjoint.in");
 ofstream g("disjoint.out");
 f>>n>>m;
 for(i=1;i<=n;i++)
   v[i]=i;
 for(i=1;i<=m;i++)
    {f>>cod>>x>>y;
     if(cod==1)  reun(x,y);
       else      if(cauta(x)==cauta(y))  g<<"DA"<<endl;
                    else                 g<<"NU"<<endl;
     } 
 f.close();
 g.close();
 return 0;
}

[•klamathix]

Ii multumim lui Petru Trimbitas pentru imbunatatirea testelor acestei probleme! 

[•RaduGabriel2012]

De ce nu se mai pot trimite surse la problema asta ?

[•thinkphp]

Aici este o portiune de cod desprinsa din programul principal; in urma compilarii primesc mesajul "evaluare completa: 40 de puncte"

    while( M-- ) {

            fin>>type>>x>>y;
           
            if(type == 1) forest.unite(x, y);
 
                      else if( forest.same(x, y) ) fout<<"DA"<<endl;

                                       else       
                                                   fout<<"NU"<<endl; 
    };

Daca modific bucata aceasta de cod usor inlocuind "endl" cu "\n", primesc evaluare completa: 100 de puncte.

    while( M-- ) {

            fin>>type>>x>>y;
           
            if(type == 1) forest.unite(x, y);
 
                      else if( forest.same(x, y) ) fout<<"DA\n";

                                       else       
                                                   fout<<"NU\n"; 
    };

[•SebiSebi]

Nu mai folosi endl. Încearcă sa pui '\n' ca sa scapi de TLE.

[•retrograd]

Am o intrebare:

Daca am vizualiza structura ca un arbore, la o operatie de Find(x) cu comprimarea drumului, nu vor fi sterse toate muchiile de pe lantul de la radacina la nod (in afara de cea directa)? In cazul asta, nicio muchie nu va fi vizitata de mai mult de doua ori, deci complexitatea ar trebui sa fie lineara (amortizata cel putin). Imi scapa ceva?

[•SebiSebi]

Nu chiar. Gândește-te ce se întâmpla când unesti 2 arbori. Dupa unire atunci când faci un Find se poate sa vizitezi anumite muchii pe care le-ai vizitat mai înainte.