RodneyX

并查集是一種簡單而有用的數(shù)據(jù)結(jié)構(gòu)，一般是用數(shù)組來實(shí)現(xiàn)，數(shù)組下標(biāo)是元素編號，而數(shù)組內(nèi)容存儲的是元素所在集合的根（或者是按樹形組織下的該元素前驅(qū)，而根這個概念本身也是樹這一數(shù)據(jù)結(jié)構(gòu)的概念）

并查集的操作非常簡單包括初始化并查集，查詢元素所屬的集合（用根元素來標(biāo)識一個集合），合并兩個不相交的集合

1. 初始化并查集：在以數(shù)組下標(biāo)為元素編號的情況下，初始化需要將每個元素作為一個集合，所以可以將數(shù)組元素全部置為-1這一非法下標(biāo)值，事實(shí)上數(shù)組下標(biāo)未根元素的值的絕對值就是集合所含元素個數(shù)

2. 查詢元素所屬的集合：數(shù)組存儲的是下標(biāo)元素對應(yīng)的前驅(qū)，所以一直往前找到根元素即可

3. 合并兩個不相交的集合：只需將一個集合的根元素前驅(qū)設(shè)置為另一集合的根即可

針對并查集有兩種優(yōu)化，都是為了讓查詢路勁盡可能短，包括路徑壓縮以及按秩合并

1. 路徑壓縮：在查詢某元素的根時，可以將這個元素以及查詢路徑上的元素的前驅(qū)置為根

2. 按秩合并：合并時將元素數(shù)量小的集合合并到大集合中

所以有如下實(shí)現(xiàn)

void init_disjointSet(int S[], int size)
{
    for (int i = 0; i < size; ++i)
        S[i] = -1;
}

int root_disjointSet(int S[], int size, int x)	//這個函數(shù)名一般為find
{
    if (x < 0 || x >= size)
        return -1;
    /* 被注釋掉的是未優(yōu)化實(shí)現(xiàn)
    while(S[x] >= 0)
        x = S[x];
    */
    int root_x = x;
    while (S[root_x] >= 0) // 查詢所在集合
        root_x = S[root_x];
    int current;
    while (S[x] >= 0)  // 執(zhí)行路徑壓縮
    {
        current = x;
        x = S[x]; // x指向其父節(jié)點(diǎn)
        S[current] = root_x;
    }
    return root_x;
}

int union_disjointSet(int S[], int size, int x, int y)
{
    if (x < 0 || x >= size || y < 0 || y >= size)
        return -1;
    int root_x = root_disjointSet(S, size, x), root_y = root_disjointSet(S, size, y);
    if (root_x == root_y)  // 是兩個不同集合才能合并
        return -1;
    /* 被注釋掉的是未優(yōu)化實(shí)現(xiàn)
    S[root_x] += S[root_y];
    S[root_y] = root_x;
    */
    if (S[root_x] < S[root_y])
    { // x根下節(jié)點(diǎn)多
        S[root_x] += S[root_y];
        S[root_y] = root_x; // 將小樹y加入大樹x
    }
    else
    {
        S[root_y] += S[root_x];
        S[root_x] = root_y;
    }

    return 1;
}