浅谈并查集优化

并查集是一种可以动态维护若干个不重叠的集合，并资瓷合并与查询的数据结构（这么水不配叫数据结构）

（接下来的内容过于菜，请大佬出门左转）

并查集最基本的操作是查询与合并，为了提高效率，我们常用的我们引入了路径压缩与按秩合并两种思想

路径压缩（最常用）：

int get(int x){
    if(x==f[x])return x;
    f[x]=get(f[x]);
    return f[x];
} 
void unionn(int x,int y){
    int u=get(x),v=get(y);
    if(u!=v)f[u]=v;
}

给大家放张图理解下路径压缩的工作原理：

路径压缩的效率很高，可以做到log级别，可以防止树的形态变为一条链，在一般并查集中应用很广泛，一旦使用路径压缩，原有的父子关系就会被破坏，从而直接建立与祖先的父子关系，可以高效地维护集合之间的从属关系，但是对于每个节点之间的直接关系是不能维护的

路径压缩这里不再过多解释毕竟这么简单，我们来简述一下按秩合并，按秩合并分为按大小合并和按深度合并两种，按大小合并是很容易想到也很容易维护的，而按深度合并则是要将整个体系的从属关系抽象成一棵树，每次将深度小的合并到深度较大的树上，这样的话不论深度小的那棵树有多深，合并后的树的深度都不会大于一开始时的较大深度。

按秩合并：

int get(int x){
    while(f[x])x=f[x];
    return x;
}
void unionn(int x,int y){//按大小合并
    int u=get(x),v=get(y);
    if(u!=v){
        if(size[u]<size[v]){
            f[u]=v;
            size[v]+=size[u];
            //按大小合并每次要更新大小 
        }
        else{
            f[v]=u;
            size[u]+=size[v];
        }
    }
}

void unionn(int x,int y){//按深度合并
    int u=get(x),v=get(y);
    if(u!=v){
        if(high[u]<hige[v])f[u]=v;
        else {
            f[v]=u;
            if(high[u]==high[v])high[u]++;
            //按深度合并只有在两树高度相等的时候更新
        }
    }
}

而按秩合并与树的形态关系很密切，虽然不能像路径压缩一样快速处理两点是否有从属关系，它能很好地维护树的形态与父子关系，可以维护出每个子节点的直接父亲，这是路径压缩所不能做到的，由此来看，两种优化方式可以说是各有千秋。

这两种方法多数情况下是可以一起用的，既用路径压缩，又用按秩合并当然可以提高效率，复杂度增长速度为为阿克曼函数的反函数，不过只用路径压缩达到的效果(log)在多数情况下也可以与之媲美，当然啦，依照个人习惯而定，愿意两个都用的当然可以，不过有时候按秩合并是不能与路径压缩一起使用的。仔细想一想我们刚才说到的性质，如果题目需要维护明确的父子关系而用到了按秩合并的话，是不能用路径压缩的，像上边所说，一旦用了路径压缩，会破坏树的形态，原来的节点会直接压缩到祖先上，这样一来我们调用的时候父子关系发生了改变，造成了算法的错误。

那么基础就讲到这里，下面看一下经典的扩展域和边带权问题

扩展域

首先让我们从一道题目入手：
放一道老题 食物链

因为题目告诉我们每三种动物构成一条食物链，我们可以将每种动物分成三部分，即同类self、捕食eat、天敌enemy，，那我们不妨将并查集数组开大三倍，作为并查集的扩展域。 即本身对应第一倍，猎物对应第二倍，天敌对应第三倍
嗯，举个栗子
如果是同类，就合并他们本身，他们的敌人,他们的猎物

    unionn(x,y);
    unionn(x+n,y+n)
    unionn(x+2*n,y+2*n);
    //(n为一倍大小）

如果x吃y，说明x是y的天敌，那x的天敌就是y捕食的物种，也就是x吃y，y吃z，z吃x

    unionn(x+n,y);
    unionn(x,y+2*n);
    unionn(x+2*n,y+n);

每次先判断是不是假话，也就是看一下是否已经被合并过，并且之前合并的关系与当前关系是否冲突，然后就可以按照题目所给出的关系进行合并啦~
在做这道题之前不妨先做一下这道题 团伙
食物链是这道题运用的反集思想的扩展，(食物链用的是三倍空间，团伙用的是二倍)做完这道题再来做食物链可能更好理解（双倍经验）

边带权

依然从一道老掉牙的题目开始 银河英雄传说 因为在并查集中存在着父子关系，所以也就有了树的形态，整个并查集数组就可以看成由若干棵树组成的森林，对于每个点维护一个数组d[]保存节点x到父亲节点fa[]之间的边权。 稍微放一下伪代码（逃：

int get(int x){
    if(x==fa[x])return x;
    int f=fa[x];
    fa[x]=get(fa[x]);
    dis[x]+=dis[f];//与祖先的距离
    size[x]=size[fa[x]];//这个集合的大小
    return fa[x];
}

因为每次路径压缩后这个点都会直接指向祖先，那么，不妨直接利用路径压缩来更新d[]（就是将维护数组的过程放在路径压缩中），这样，对于每一次询问祖先都能更新对应的边权，在最后调用结果的时候重新更新一遍就能保证其正确性。 理解了的话就再来一道QwQ 叠积木（二倍经验）
代码什么的我相信你会写 （不放代码就跑真开心~）

并查集求环

由于并查集能维护父子关系，所以我们也可以将它运用到图论中，比如这道题信息传递，对于一个环，势必有一个点的父亲是他的子孙节点，（画个图很好理解的），如果发现将要成为自己父亲的节点是自己几代之后的子孙，这就说明有环出现了，用边带权并查集维护儿子是哪一代就可以求出环的大小，就可以进一步求最大环、最小环之类的东西啦，当然这只是并查集思路，这类题目还有另一种解法——tarjan（强烈安利）就是裸的缩点。 好的，如果理解了就来看下这道加强版在农场万圣节
又不放代码啦啦啦

特意去学了下可持久化并查集，发现她和并查集并没有很大的关系，所以这里不介绍啦（并不是偷懒）

以上，希望我的讲解能对大家有帮助 qwq

最后希望大家 noip2018 rp++!
估计发出来的时候我已经退役了

猛然发现之前自己做的图片挂了，感谢好心的管理大大帮我配图QAQ虽然做之前那个图片我很用心的,好可惜嘤嘤嘤（怎么感觉管理大大的图片风格很诡异2333