从0开始学算法--基础数据结构（2.8并查集）

算法理解：

根据名字就能很好的理解这个算法，集合的合并和查询

合并什么？查询什么？

合并操作为：把x所在的集合和y所在的集合合并为一个集合。查询x和y是否在一个集合里。

如：元素为1-n，这n个元素分别在编号为1-n的集合中。如果将3和5合并成为一个集合，只需要将元素3指向元素5即可

现在把元素5和元素2所在的集合合并合并，5指向2

 可以看到如果要查询2和3是不是在一个集合中，只需要查询2和3的祖先是不是同一个元素就可以了

查询祖先代码

//f[x]初始化为f[i]=i;
int find_set(int x){
    while(x!=f[x])x=f[x];
    return x;
}

优化一：可以看到合并集合时本质是形成了一颗集合树，用树顶的元素代表这个集合，既然是树那么时间复杂度就和树的深度有关系，在合并时尽可能的让树的深度小一些就可以减少时间复杂度，这种方法叫做按秩合并

void unite(int a,int b{
    int x=find_set(a);
    int y=find_set(b);
    if(x==y)return;//x和y在一个集合中，不用合并
    if(rank[x]<rank[y]){//rank为树深
        f[x]=y;
    }else{
        f[y]=x;
        if(rank[x]==rank[y]){
            rank[x]++;
        }
    }
}

优化二：在查询祖先时，我们访问了树上祖先到这个节点的所有节点，那么我们让这些节点的所有节点都直接指向祖先节点就可以大大的减少时间复杂度。

int find_set(int x){
    return f[x]==x?x:f[x]=find_set(f[x]);
}

例题：题目链接 poj2524

当今世界上有许多不同的宗教，要了解它们是很困难的。你想知道你们学校的学生信仰多少种不同的宗教。你知道你们学校有n个学生(0 <n(= 50000))。你不可能问每个学生的宗教信仰。此外，许多学生对表达他们的信仰感到不自在。避免这些问题的一种方法是问m (0 <=m (= n(n-1)/2)对学生，问他们是否信仰相同的宗教(例如，他们可能知道他们是否参加同一个教堂)。从这些数据中，你可能不知道每个人都信仰什么，但你可以了解校园里可能代表多少种不同宗教的上限。你可能认为每个学生最多只信奉一种宗教。

输入输入由许多情况组成。下面的m行分别由两个整数i和j组成，指定学生i和j信仰同一宗教。学生们编号为1至n.输入端由n=m=0的行指定。

输出对于每个测试用例，在一行中打印案例编号(从1开始)，然后是该大学学生信仰的不同宗教的最大数量。

Sample Input

9
2
3
4
5
6
7
8
9
10
4
3
5
8
8
0

Sample Output

Case 1: 1
Case 2: 7

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;
int disjoint_set[50010];
int a[50010];
int findset(int x){
    return disjoint_set[x]!=x?disjoint_set[x]=findset(disjoint_set[x]):x;
}

int readint(){
    int x;scanf("%d",&x);return x;
}

int main(){
    int n,m;
    int ss=0;
    while(~scanf("%d%d",&n,&m)){
            ss++;
        if(n==0&&m==0)break;
        for(int i=1;i<=n;i++){
            disjoint_set[i]=i;
            a[i]=0;
        }
        for(int i=0,v,c;i<m;i++){
            scanf("%d%d",&v,&c);
            int x=findset(v);
            int y=findset(c);
            if(x!=y){
                disjoint_set[x]=y;
            }
        }
        for(int i=1;i<=n;i++){
            a[findset(i)]=1;
        }
        int sum=0;
        for(int i=1;i<=n;i++){
            if(a[i]==1)sum++;
        }
        printf("Case %d: ",ss);
        printf("%d\n",sum);
    }
    return 0;
}

注释：优化一与优化二各有优劣，优化1的优点在于每次只改变了f[]数组的一个值，优化二的优点在于时间复杂度较低