Zbiory rozłączne

Zbiory rozłączne (lasy rozłączne)

Struktura zbiorów rozłącznych pozwala w wydajny sposób sprawdzić, czy dwa elementy należą do tych samych, czy różnych zbiorów oraz w razie potrzeby połączyć te zbiory w jeden.

Struktura ta ma zastosowanie przy sprawdzaniu spójności grafu, w algorytmie wyszukiwania minimalnego drzewa rozpinającego (algorytm Kruskala) czy w rozpoznawaniu obszarów w obrazach cyfrowych.

Zarys algorytmu

Idea algorytmu opiera się ustaleniu jednego elementu, który jest reprezentantem danego zbioru. Każdy element danego zbioru wskazuje właśnie na niego. Połączenie dwóch zbiorów polega na ustaleniu jednego reprezentanta tych dwóch zbiorów. Zazwyczaj do zbioru liczniejszego dołączany jest zbiór o mniejszej liczbie elementów.

Do implementacji użyto dwóch funkcji:

• FIND(a) — funkcja wyszukuje reprezentanta dla elementu a
• UNION(a, b) — funkcja sprawdza, czy element a i b należą do różnych zbiorów i jeśli odpowiedź jest twierdząca, to łączy je w jeden.

Zadanie "ZNAJOMI"

Na pewnym dobrze znanym ci portalu społecznościowym baza danych użytkowników jest bardzo duża. Zastanawiałeś się może, czy da się dotrzeć do każdego użytkownika, który nie jest bezpośrednio twoim znajomym, ale jest znajomym, któregoś z twoich znajomych lub znajomym znajomego twojego znajomego itd.. W tym zadaniu należy wyznaczyć najbardziej liczny zbiór osób utworzony w myśl maksymy "Znajomy mojego znajomego jest moim znajomym".

Wejście

W pierwszym wierszu dwie liczby n i m, gdzie n to liczba wszystkich użytkowników serwisu (1 ≤ n ≤ 100000), a m to liczba par osób, które się znają (1 ≤ m ≤ 500000). Każdy z kolejnych m wierszy składa się z dwóch liczb całkowitych a i b (1 ≤ a, b ≤ n, a≠b), które opisują, że użytkownicy a i b są znajomymi. Relacja znajomości w rozumieniu Jasia jest symetryczna i przechodnia.

Wyjście

Jedna liczba oznaczająca liczebność największej grupy znajomych w serwisie.

//Zbiory rozłączne
//Zadanie: Znajomi
//algorytm.edu.pl
#include<bits/stdc++.h>
using namespace std;

int *rep, *moc_zbioru;

int Find(int a)
{
	if(rep[a] != a) 
		rep[a] = Find(rep[a]);
	return rep[a];
}

void Union(int a,int b)
{
	//jeśli liczby a i b należą do różnych zbiorów, to je połącz w jeden
	int fa = Find(a), fb = Find(b);
	if(fa != fb)
	{
		if(moc_zbioru[fa] < moc_zbioru[fb]) //dołączamy mniejszy zbiór do większego
			swap(fa, fb);
		rep[fb] = fa;		//ustawienie nowego reprezentanta
		moc_zbioru[fa] += moc_zbioru[fb]; //powiększenie większego zbioru o liczbę elementów mniejszego zbioru
		//(*)
	}
}

int main()
{
	int n, m, a, b;
	
	//cout<<"Podaj liczbę znajomych oraz liczbę relacji między nimi: ";
	cin>>n>>m;
	
	rep = new int [n+1];
	moc_zbioru = new int [n+1];
	
	//na początku każdy element jest swoim reprezentantem
	for(int i=0;i<=n;i++)
	{
		rep[i] = i; 		//ity indeks jest równy swojej wartości
		moc_zbioru[i] = 1;	//zbiory są jednoelementowe
	}

	//łączenie w zbiory
	while(m--)
	{
		cin>>a>>b;
		Union(a, b);
	}

	//wyszukiwanie wartości największej
	//można to zrobić w funkcji Union w (*)
	int Max = 0;
	for(int i=0;i<=n;i++)
		Max = max(Max, moc_zbioru[i]);
	
	cout<<Max;
	
	return 0;
}

Przykład:

Wejście:

9 7
2 1
1 9
3 4
4 5
7 5
4 8
4 7

Wyjście:

5