• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Paduri de multimi disjuncte

0
  • Publicat de salexandru92
  • în C/C++ · Probleme algoritmică · Tehnic
  • — 26 oct., 2010 at 11:00 am

Notiuni introductive

Folosind aceasta structura de date ne propunem sa rezolvam foarte eficient urmatoarele probleme :

• Daca doua obiecte x si y fac parte din aceeasi multime? Din ce multime face parte obiectul x ?
• Sa se reuneasca multimile y si z.

Pentru simplitate si fara a restrange generalitatea vom considera ca elementele unei multimi, S, sunt numere de la 1 la N.
Hai sa luam ca exemplu multimea S={ 1, 2,…,10 } si submultimile S1={ 1, 2, 4 }, S2={ 5, 6, 9, 10 }, S3={ 7, 8 }( de remarcat ca multimile S1, S2 si S3 intersectate dau multimea S si sunt disjuncte intre ele, adica nu au nici un element comun ). Fiecare din multimile S1, S2, S3 le vom reprezenta ca pe un arbore cu radacina, astfel o posibila reprezentare este :

Desi din desene nu reiese, arborele nu trebuie sa fie binar, fiecare nod poate sa aibe o infinitate de fii.

Un arbore il vom reprezenta prin vectorul de tati. Fie f un vector, f[i] semnifica tatal elementului i, daca i este radacina arborelui atunci f[i]=i. Pentru arbori de mai sus avem vectorul f o sa contina :

f[1]=1
f[2]=4
f[3]=9
f[4]=1
f[5]=6
f[6]=9
f[7]=7
f[8]=7
f[9]=9
f[10]=6

Acum, pentru a vedea daca doua elemente, x si y, sunt din aceeasi multime sau nu vom compara radacinile arborilor din care fac parte: daca radacinile sunt egale atunci fac parte din aceeasi multime. Pentru asta ne vom folosi de vectorul f, f[x] reprezinta tatal lui x, f[f[x]] reprezinta tatal lui f[x], f[f[f[x]] reprezinta tatal lui f[f[x]] … vom continua asa pana cand f[x]=x => am dat de radacina.

int Find( int x )
{
     for( x=f[x]; x != f[x]; x=f[x] ); //urcam pe nivele in arbore
     return x;
}

Aceasta functie are complexitatea O(h), unde h este nivelul la care se afla x in arbore. Vom face o imbunatatire, care se bazeaza pe faptul ca pe noi ne intereseaza doar radacina arborelui, asa ca vom compresa drumurile. Ce inseamna asta ? Dupa ce determinam radacina arborelui putem lega restul elementelor direct de el si asa vom avea acces
direct la radacina acestui arbore.

int Find( int x )
{
      int y, z; //in y voi retine radacina arborelui
      for( y=f[x]; y != f[y]; y=f[y] ); //determin radacina
         while( x != f[x] ) //acum compresam drumurile
          {
           z=f[x];
          f[x]=y; //leg elementul x cu radacina arborelui, y
          x=z;
    }
    return y; //returnez radacina
 }

Pentru a uni doua multimi mai avem nevoie de un vector. Vom mai folosi un vector r, unde r[i] semnifica numarul de nivele din arbore. Arbori S1 si S2 au 3 nivele, iar S3 are 2, deci vectorul r ar contine :

r[1]=r[4]=r[2]=3;
r[9]=r[6]=r[10]=r[5]=r[3]=3;
r[7]=r[8]=2;

Pentru a uni doua multimi vom respecta Regula Ponderilor care afirma :

„Daca numarul de nivele din arborele cu radacina x este mai mic decat numarul de niveluri din arborele cu radacina y, atunci y va devein parintele lui x; altfel, x va devein parintele lui y. „

Repsectand acest lucru, codul devine :

void  Union( int x, int y ) //!important x si y sunt radacini ai unor arbori.
{
	if(  r[x] <= r[y] )
	   f[x]=y;
	else  f[y]=x;
	if(  r[x] == r[y] )
	    ++r[y];
}

Problema rezolvata

Acuma, dupa atata teorie va propun sa rezolvam urmatoarea problema simpla :
Se da un graf neorientat G, cu N noduri si M muchii. Pe acest graf se pot executa doua operatii :

1 : Se raspunde la umratoarea intrebare: Nodul x si y fac parte din aceeasi componenta conexa ? ( DA sau NU )
2 : Se introduce muchia [ x, y ].
1 <= N <= 100000
1 <= M <= 500000
Numarul de operatii de tip 1 si 2 <= 100000

Pentru a determina o componenta conexa vom folosi o parcurgere DF. Vom porni de la un nod x, cu x de la 1 la n , si determinam toate nodurile la care pot ajunge din x. Aceste noduri vor face parte din aceeasi componenta conexa.

Tot in timpul parcurgeri DF vom construi vectorul f, toate elemente care fac parte din aceeasi componenta conexa vor avea ca tata pe x, nodul de la care ma pornit, iar r va fi initializat cu 2( intrucat arborele multimii are 2 nivele, pe nivelul 1 este radacina x, iar restu se afla pe nivelul 2 ).

Vom mai folosi un vector cc, care semnficia din ce componenta conexa face parte nodul x.

            #include < vector >
            #include < fstream >
            #include < cstdlib >
            #define MAX_N 100011

            using namespace std;
            /*
             *
             */
             vector< int > G[MAX_N];
             int f[MAX_N], r[MAX_N], cc[MAX_N];
             int Find( int x )
             {
             	int y, z;
              	for( y=f[x]; y != f[y]; y=f[y] );
                while( x != f[x] )
                {
                	z=f[x];
                    f[x]=y;
                    x=z;
                }
                return y;
             }
             int Union( int x, int y )
             {
             	if( r[x] <= r[y] )
                 	f[x]=y;
                else f[y]=x;
                if( r[x] == r[y] )
                	++r[y];
             }
             inline void DFS( int x, int father )
             {
             	f[x]=father;
                r[x]=2;
             	vector < int >::iterator it=G[x].begin(), iend=G[x].end();
                for( ; it < iend; ++it )
                	if( !f[*it] ) //daca nodul *it n-a mai fost vizita
           	     DFS(*it);
             }
             int main( void )
             {
             	int N, M, Q, x, y, nr_cc=0;
                ifstream in( "input.in" );
                for( in>>N>>M; M; --M )
                {
                	in>>x>>y;
                    G[x].push_back(y);
                    G[y].push_back(x);
                }
                for( x=1; x <= N; ++x )
                	if( !f[x] ) //x nu a fost vizitat pana acuma
                    {
				cc[x]=++nr_cc;
                    	DFS(x); //determin toate nodurile la care pot ajunge din x, ele vor forma o componenta conexa
                    }
                for( in>>Q; Q; --Q )
                {
                    in>>i>>x>>y;
                    if( 1 == x )
                    {
                    	cout<<( find(x) == find(y) ? "DA\n" : "NU\n" );
                    }
                    else {
                    		 x=find(x); y=find(y);
                             if( x != y ) //daca x si y nu fac parte din aceeasi componenta conexa, atunci adaugare muchiei [x,y] va uni cele 2 componente
                             	Union( x, y );
                    	 }
                }
                return EXTI_SUCCESS;
             }

Probleme de rezolvat

  • Joker
  • Infoarena
  • Imbunatatiti algoritmul lui Kruskal prezentat aici
  • Ce complexitate are algoritmul prezentat la punctul II ?

Daca acest articol contine o greseala, selecteaza cuvintele sau fraza gresita si tasteaza combinatia de taste Shift + Enter sau apasa click aici pentru a o raporta. Multumim!

Etichete: algoritmicaarboreC++multimi disjunctepaduri de multimi disjuncteprogramare

— Alexandru S a scris 1 articol

Buna, ma numesc Alexandru si sunt elev in clasa a XII. Programarea este una din marile mele pasiuni, niciodata nu refuz o provacare ;)

  • Articolul anterior WorldIT.info a schimbat termenii si conditiile de partajare a informatiilor
  • Articolul următor Google Feedburner vine cu o interfata moderna

  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    • imacoolat-curat.ro
      | Published: februarie 3, 2020 - 2:00 am
    • hotel-palace.ro
      | Published: februarie 2, 2020 - 2:00 am
    • www.tahometru.ro
      | Published: februarie 1, 2020 - 2:00 am
    • alexisart.ro
      | Published: ianuarie 30, 2020 - 2:00 am
    • justshop.ro
      | Published: ianuarie 29, 2020 - 2:00 am
    RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • ianuarie 2021
    L Ma Mi J V S D
    « dec.    
     123
    45678910
    11121314151617
    18192021222324
    25262728293031
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Paduri de multimi disjuncte
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons

Multumim foarte mult ca ne-ai raportat greseala! O vom remedia in cel mai scurt timp posibil.