UNION FIND

RNO-Wiki

Union-Find to bardzo ciekawa struktura dla zbiorów rozłącznych.

Początkowo mamy <math>n</math> zbiorów rozłącznych <math>\{1\}, \{2\}, \ldots, \{n\}</math>. Struktura UF pozwala wykonywać następujące operacje:

  • union(a,b) - połącz zbiory, zawierające a i b
  • find(a) - zwraca pewną liczbę charakterystyczną dla zbioru, tzw. reprezentanta zbioru.
    Chodzi o to, że dla dwóch elementów a,b z tego samego zbioru będzie find(a)==find(b), a dla dwóch elementów które nie należą do tego samego zbioru będzie find(a)!=find(b)


Analiza tej struktury jest bardzo trudna. Można dowieść, że n operacji union, find działają w czasie zamortyzowany O(n log*(n)), czyli prawie liniowym (nie do odróżnienia na dzisiejszych komputerach). Wygląda na to, że pojedyncze operacje union, find, działają prawie zawsze w czasie stałym. Super, co nie?

Powyższe wyniki można uzyskać dzięki specjalnej implementacji struktury.

Najpiękniejszą zaletą tej struktury jest to, że można ją zaimplementować w 2 minuty.

Oto przykład programu. Komentarze wyjaśnią wszystko. 

#include<iostream>
using namespace std;
 
/*
	Rafał Nowak
	2007.01.05
 
  Struktura danych UNION-FIND dla zbiorów rozłącznych
*/
int tab[100000], ile[100000]; // 100000 - to liczba wszystkich elementów
 
int Find(int a)
{
	if (tab[a]==a) return a; // jesli a jest reprezentantem zbioru zawierajacego a to zwracamy a
	// W przeciwnym wypadku pytamy sie kto jest reprezentantem zbioru zawierajacego tab[a], bo w koncu to ten sam zbior :-)
	int fa = Find(tab[a]);
	tab[a] = fa; // zaktualizujmy wartosc tab[a] na nowszą!, w razie czego, gdyby ktoś się pytał kiedyś jeszcze raz o find(a)
	return fa;
}
 
bool Union(int a, int b) // niestety słowo union (z małej litery) jest słowem kluczowym. Ciekawe, czy ktoś w ogóle je używa?
{
	int fa = Find(a); // szukaj reprezentanta zbioru zawierającego element 'a'
	int fb = Find(b); // szukaj reprezentanta zbioru zawierającego element 'b'
 
	if (fa==fb) return false; // nie trzeba nic łączyć
	if (ile[fa] <= ile[fb])
	{
		ile[fb] += ile[fa];
		tab[fa] = fb;
	}
	else
	{
		ile[fa] += ile[fb];
		tab[fb] = fa;
	}
	return true;
}
 
int main(void)
{
	/*
	Na poczatku mamy n zbiorów rozłącznych : każdy ma jeden elelement
	{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}
	*/
 
	int n = 10;
	for (int i=0; i<n; i++)
	{
		tab[i] = i; // reprezentantem zbioru zawierającego element 'i' jest np 'i' (nikt inny być nie może :-)
		ile[i] = 1; // jeden element; chyba jasne co nie?
	}
 
    // A teraz bawimy się
	int a,b;
 
//	Jak sprawdzić, czy 5 i 6 są w tym samym zbiorze?
	a = Find(5);
	b = Find(6);
	if ( a != b ) { printf("5 i 6 sa w roznych zbiorach\n"); }
 
//	No to połączmy te zbiory :-)
	Union(a,b); // i już :-)
	if ( Find(5) == Find(6) ) { printf("5 i 6 sa juz w tym samym zbiorze\n"); }
//	Mamy więc sytuację :    
//	{0}, {1}, {2}, {3}, {4}, {5,6}, {7}, {8}, {9}
 
    Union(0,8);
 
    Union(2,4);
 
    Union(8,3);
 
//	co mamy?
//	Oczywiście, że
//	{0,3,8}, {1}, {2,4}, {5,6}, {7}, {9}
 
	if ( Find(2) != Find(6) ) { printf("2 i 6 są w roznych zbiorach\n"); }
	Union(2,6);
//	{0,3,8}, {1}, {2,4,5,6}, {7}, {9}
	if ( Find(2) == Find(6) ) { printf("2 i 6 są w tych samych zbiorach\n"); }	    
 
	Union(0,9);
//	{0,3,8,9}, {1}, {2,4,5,6}, {7}
	if ( Union(3,9) == false ) { printf("Union jest funkcja ktora zwraca false jesli nie trzeba bylo laczyc zbiorow.\n"); }
 
	Union(1,7);
//	{0,3,8,9}, {1,7}, {2,4,5,6}
	if ( Find(3) != Find(4) ) { printf("3 i 4 są w roznych zbiorach\n"); }
 
	a = ile[ Find(3) ]; // tablica ile trzyma licznosc zbiorow zawierajacych reprezentanow.
	printf("Element 3 jest w zbiorze, ktorego reprezentantem jest %d. Zbior ten ma %d elementow.\n", Find(3), a );
 
	Union(3,4);
//	{0,2,3,4,5,6,8,9}, {1,7}, 
	if ( Find(0) != Find(7) ) { printf("0 i 7 są w roznych zbiorach\n"); }
	Union(0,7);
 
//	Wykonalismy n-1 operacji UNION, a wiec polaczylismy wszystkie elementy w jeden zbior
    return 0;
}
Źródło: "http://www.rafalnowak.pl/wiki/index.php?title=UNION_FIND"