并查集

并查集的数据结构

1
int S[MAXSIZE];

查询元素所在的集合

1
2
3
4
5
6
7
int Find(int sets[],int x){
    int index=x;
    while(sets[index]!=-1){
        index=sets[index];
    }
    return index;
}

合并两个集合

1
2
3
4
void Union(int sets[],int root1,int root2){
    if(root1==root2)    return;
    sets[root2]=root1;
}

并查集和优化

Union优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*将两个根节点所在的集合合并集合*/
void UnionSets(int sets[],int root1,int root2){
    if(root1==root2)    return;
    if(sets[root1]>=sets[root2]){
        sets[root1]+=sets[root2];/*累加树的结点*/
        sets[root2]=root1;/*小树挂载到大树*/
    }
    else{
        sets[root2]+=sets[root1];
        sets[root1]=root2;
    }
}
/*合并两个元素所在的集合*/
void Union(int sets[],int node1,int node2){
    int root1=Find(sets,node1);
    int root2=Find(sets,node2);
    UnionSets(sets,root1,root2);
}

Find优化

使用压缩路径优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*查找元素所在集合*/
int Find(int sets[],int x){
    int root=x;
    /*找到根节点*/
    while(sets[root]>=0)
        root=sets[root];
    int tmp=x;
    while(sets[tmp]>=0){
        int t=sets[tmp];/*保存父节点*/
        sets[tmp]=root; /*挂载到根节点*/
        tmp=t;/*成为父节点*/
    }
    return tmp;
}