Playground
#include <iostream> #include <cstring> using namespace std; const int MAX_N = 101; int leader[MAX_N]; int ranking[MAX_N]; int Find(int X) { if (leader[X] != X) { int setLeader = Find(leader[X]); //prashaj go leader[X] //zapameti go rezultatot (podobruvanje) leader[X] = setLeader; } return leader[X]; } void Union(int X, int Y) { int setLeaderX = Find(X); int setLeaderY = Find(Y); if (setLeaderX == setLeaderY) { return /* vekje se vo istoto mnozhestvo */; } if (ranking[setLeaderX] == ranking[setLeaderY]) { //ist rang, pa mozheme da izbereme eden od niv za spojuvanjeto leader[setLeaderY] = setLeaderX; //rangot sega kje se zgolemi ranking[setLeaderX]++; } else { //razlichen rang, spoi vo ona so povisok (bez menuvanje na ranking[]) if (ranking[setLeaderX] > ranking[setLeaderY]) { leader[setLeaderY] = setLeaderX; } else { leader[setLeaderX] = setLeaderY; } } } int main() { int N = 5; for (int i=0; i<N; i++) { //inicijalno, site si se vo svoe sopstveno mnozhestvo leader[i] = i; } //inicijalno, sekoe mnozhestvo dobiva rang 0 memset(ranking, 0, sizeof(ranking)); //da izvrshime nekolku operacii if (Find(0) != Find(1)) { //ova kje se otpechati cout << "0 and 1 are in different sets." << endl; } Union(0, 1); if (Find(0) == Find(1)) { //ova kje se otpechati cout << "Now, 0 and 1 are in the same set." << endl; } if (Find(0) != Find(2)) { //ova kje se otpechati cout << "0 and 2 are in different sets." << endl; } Union(2, 3); Union(2, 4); //tuka, imame dve mnozhestva [0, 1], i [2, 3, 4] if (Find(0) != Find(2)) { //ova kje se otpechati cout << "0 and 2 are in different sets." << endl; } Union(0, 4); //tuka, imame samo edno mnozhestvo [0, 1, 2, 3, 4] if (Find(0) == Find(3)) { //ova kje se otpechati cout << "0 and 3 are in the same set." << endl; } return 0; }
Input data
Program output
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!