Union Find Set(并查集): 基本操作(优势)：1. 查找某个元素所在的集合; 2. 合并两个不相交的集合。 目前看到比较多的实现都是基于数组的。

find_union_set.cpp

// Union Find Set

const int MAXN = 100;
int father[MAXN] = {0};
int rank[MAXN] = {0};

int find_set(const int x)
{
    if (father[x] != x)
    {
        father[x] = find_set(father[x]);
    }
    return father[x];
}

void union(const int x, const int y)
{
    const int fx = find_set(x);
    const int fy = find_set(y);
    
    if (fx == fy)
    {
        return;
    }
    else if (rank[fx] < rank[fy])
    {
        father[fx] = fy;
        ++rank[fy];
    }
    else
    {
        father[fy] = fx;
        ++rank[fx];
    }
}

bool is_in_same_set(const int x, const int y)
{
    return find_set(x) == find_set(y);    
}

int main()
{
    for (int i = 0; i < MAXN; ++i)
    {
        father[i] = i;
    }
    return 0;
}