Paduri de multimi disjuncte
0Notiuni 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
