Zbiory Rozłączne

Artykuł w budowie!

Zbiory rozłączne – dwa zbiory są rozłączne, gdy ich część wspólna jest zbiorem pustym. Inaczej mówiąc, zbiory te nie mają ani jednego wspólnego elementu.
Na przykład, zbiory {2, 4, 6} i {3, 5} są rozłączne, natomiast {2, 4, 6} i {3, 4, 5} – nie.

Przykładowy kod:

#include <vector>
 
using namespace std;
 
vector<int> ojciec, ranga;
 
void make_set (int x)
{
    ojciec[x] = x;
    ranga[x] = 0;
}
 
void link (int x, int y)
{
    if (ranga[x] > ranga[y])
        ojciec[y] = x;
    else
    {
        ojciec[x] = y;
        if (ranga[x] == ranga[y])
            ++ranga[y];
    }
}
 
int find_set (int x)
{
    if (x != ojciec[x])
        ojciec[x] = find_set(ojciec[x]);
 
    return ojciec[x];
}
 
void union (int x, int y)
{
    link(find_set(x), find_set(y));
}
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License