C语言实现并查集

通过压缩路径，优化find
通过小树合并大树，优化Union

#define SIZE 100
int S[SIZE];

void Init(int S[])
{
    for (int i = 0; i < S.length; i++)
    {
        S[i] = -1;
    }
}

//未优化的Find
int Find(int S[], int x)
{
    while (S[x] >= 0)
    {
        x = S[x];
    }
    return x;
}
//未优化的Union
void Union(int S[], int Root1, int Root2)
{
    if (Root1 == Root2)
        return;
    //小树并到大树
    S[Root2] = Root1;
}

//压缩路径优化，优化Find
int Find2(int S[], int x)
{
    int root = x;
    while (S[root] >= 0)
        root = S[root]; //找到根结点
    while (x != root)
    {
        int pre = S[x]; //找到前驱（父节点）
        S[x] = root;    //将结点挂在根结点下
        x = pre;        //父结点继续跟刚才一样操作
    }
}

//小树合并大树下进行优化，优化Union
void Union2(int S[], int Root1, int Root2)
{
    if (Root1 == Root2)
        return;
    if (S[Root2] > S[Root1]) // R2为小树，R1大树
    {
        S[Root1] += S[Root2];
        S[Root2] = Root1;
    }
    else
    {
        // R1为小树，R2大树
        S[Root2] += S[Root1];
        S[Root1] = Root2;
    }
}