1. 集合的表示

• 集合运算:交、并、补、差，判定一个元素是否属于某一集合

• 并查集:集合并、查某元素属于什么集合

• 并查集问题中集合存储如何实现?
  可以用树结构表示集合，树的每个结点代表一个集合元素

  
  

• 采用静态链表存储

  
  
  
  

typedef int ElementType;
typedef  struct {
    ElementType data;
    int parent;
}SetType;

2. 集合运算

(1) 查找某个元素所在的集合（用根结点表示）

#define MaxSize 10
int Find(SetType S[], ElementType X)
{
    int i;
    for (i = 0; i < MaxSize && S[i].data != X; i++) ;
    if(i >= MaxSize) return -1;
    for (; S[i].parent >= 0; i = S[i].parent) ;
    return i;
}

(2) 集合的并运算

• 分别找到X1和X2两个元素所在集合树的根结点。
• 如果他们不同根，则将其中一个根结点的父结点指针设置成另一个根结点的数组下标。

void Union(SetType S[], ElementType X1, ElementType X2)
{
    int root1, root2;
    root1 = Find(S, X1);
    root2 = Find(S, X2);
    if (root1 != root2) {
        S[root2].parent = root1;
    }
}

3. 集合的简化表示

• 元素值和数组下标一一对应，数组内存放父结点索引。

typedef int ElementType;
typedef int SetName; /*默认用根结点的下标作为集合名称*/
typedef ElementType SetType[];
SetName Find(SetType S, ElementType X)
{
    for (; S[X]>=0; X=S[X]);
    return X;
}
void Union(SetType S, SetName root1, SetName root2)
{
    S[root2] = root1;
}

案例

有5个电脑，输入C表示检查两个电脑是否连通，输入I表示连接两个电脑，输入S表示结束并输出有几个连通网络。

void Input_connection(SetType S)
{
    ElementType u, v;
    SetName root1, root2;
    cin >> u >> v;
    root1 = Find(S, u-1);
    root2 = Find(S, v-1);
    if (root1 != root2) {
        Union(S, root1, root2);
    }
}

void Check_connection(SetType S)
{
    ElementType u, v;
    SetName root1, root2;
    cin >> u >> v;
    root1 = Find(S, u-1);
    root2 = Find(S, v-1);
    if (root1 == root2) {
        cout<<"yes"<<endl;
    }else{
        cout<<"no"<<endl;
    }
}

void Check_network(SetType S, int n)
{
    int i, count = 0;
    for (i = 0; i < n; i++) {
        if (S[i] < 0) {
            count++;
        }
    }
    if (count == 1) {
        cout<<"The network is connected."<<endl;
    }else{
        cout<<"There are "<<count<< " components."<<endl;
    }
}
int main(int argc, const char * argv[]) {
    // insert code here...
    SetType s = {-1, -1, -1, -1, -1};
    char in;
    do{
        cout<<"请输入标识："<<endl;
        cin>>in;
        switch (in) {
            case 'I':
                Input_connection(s);
                break;
            case 'C':
                Check_connection(s);
                break;
            case 'S':
                Check_network(s, 5);
                break;
            default:
                break;
        }
    }while(in != 'S');
    
    return 0;
}

4. 按秩归并

• 前提是没有简化前的集合
• 因为我们用根结点表示集合，每次将root2 挂载到 root1上 因此树越来越高。每次查找Find(1)的根结点时需要T=O(n), 因此进行n次Union的时候时间复杂度为T = O(n²)

为什么树会越来越高？

• 将较高的树贴到较低的树上，会使树变高一层。
• 应该将较低树贴到高树上！

树高应该存在哪里呢？
可以将树根的值改成负的树高
S[Root] = -树高;

 if (S[Root2] < S[Root1]) {
        S[Root1] = Root2;
    }else{
        if (S[Root1] == S[Root2]) S[Root1]--;
        S[Root2] = Root1;
    }

另一种做法：比规模
把小树贴到大树上 S[Root] = -元素个数;

if (S[Root2] < S[Root1]) {
        S[Root2] += S[Root1];
        S[Root1] = Root2;
    }else{
       S[Root1] += S[Root2];
        S[Root2] = Root1;
    }

5. 路径压缩

路径压缩

SetName compressionPath(SetType S, ElementType X)
{
    if (S[X] < 0) {
        return X;
    }else{
        return S[X] = compressionPath(S, S[X]);
    }
}