并查集笔记

before 正片

讲之前说一下，并查集珂有用了！什么题都能用并查集乱搞！

（最基础的）正片

并查集是啥？

定义：并查集(disjoint-set data structure)分为3个部分，并，查，集。然后我们讲的顺序是集，查，并。

。。。（好沙雕）

2.珂以干嘛：

2.1 初级：珂以维护在一块的关系。打个比方，我们珂以快速求两个人是不是在同一个班里面。同时，我们也珂以记录集合里面的信息（如有多少元素等）。

2.2 升级：珂以维护种类的关系（好后面会讲），也就是敌人的敌人是朋友。

那说完这些，就要讲实现了。

首先是“集”的实现。通常，我们把它用一个森林（也就是很多个树结构）来表示。但是，我们维护的很简单，只要知道每个节点的父亲是谁就珂以了。如果一个节点的父亲是自己，说明它是祖先。初始状态每个节点都是祖先（这个不加就炸了）。如下图表示：
并查集笔记
然后是这一步的代码实现（我喜欢面向对象）：

class DSU
//DSU是并查集的英文名简写
{
    public:
        #define N 1001000
        int Father[N];
        void Init()
        {
            for(int i=0;i<N;i++)
            {
                Father[i]=i;
            }
        }
};

然后并查集就学了 $\frac{1}{3}$ 了。

接下来是如何“查”。

这个很显然，写一个递归就珂以了（我不会写非递归），不断的找，如果是祖先，就返回自己，否则就去问自己的爸爸祖先是谁，然后爸爸再问爸爸的爸爸，爸爸的爸爸再问爸爸的爸爸的爸爸的爸爸…直到没有爸爸（自己是祖先）。
代码：

//写在类里面
int Find(int x)
{
    if (x==Father[x])
    {
        return x;
    }
    else
    {
        return Find(Father[x]);
    }
}

然后并查集就学了 $\frac{2}{3}$ 了。

接下来是“并”。这也同样很简单，如果我们要并 $x$ 和 $y$ ，只要把 $x$ 的祖先的爸爸设置成 $y$ 的祖先， $x$ 就并到 $y$ 上了。代码：

//这个也写在类里面
void Merge(int x,int y)
{
    int ax=Find(x),ay=Find(y);
    Father[ax]=ay;
}

这样并查集就学了 $\frac{3}{3}$ 了。
有没有感觉很水。。。
但是我为什么不化简这个分数呢。。。因为还有 $\frac{4}{3}$ 和 $\frac{5}{3}$ 呢。。。
这两个多出来的就是两个优化。。。
具体哪两个，请看下集。

正片的优化

优化1. 路径压缩

我们会发现，在维护并查集的过程中，其实中间经过哪些父亲，并不是很重要，只要知道谁是祖先就珂以了，所以在找的过程中，直接把爸爸的爸爸设置成祖先即可（这样快了好多，理论上只要有了这个优化，不加优化2很多题都珂以过了。）
代码：

int Find(int x)
{
    if (x==Father[x])
    {
        return x;
    }
    else
    {
        Father[x]=Find(Father[x]);
        //直接接到祖先上
        return Father[x];
    }
}

优化2. 按秩合并

注释
秩：集合大小
也就是说我们把集合从小的接到大的。这样就避免了结构十分不平衡。（如果出题人故意卡你的话，结构不平衡就算路径压缩也没有用）。这句涉及到记录集合大小的问题。这也不难，只要记录一个 $Cnt$ 数组， $Cnt[i]$ 当且仅当 $i$ 为祖先的时候有用，记录以 $i$ 为祖先的集合大小。别的看代码就能懂了。注意 $Cnt$ 的初始值都是1。
代码（由于改动较大，直接贴完整代码）：

#include<bits/stdc++.h>
using namespace std;
class DSU
{
    public:
        #define N 1001000
        int Father[N];
        int Cnt[N];
        void Init()
        {
            for(int i=0;i<N;i++)
            {
                Father[i]=i;
                Cnt[i]=1;//注意初始化！
            }
        }
        int Find(int x)
        {
            if (x==Father[x])
            {
                return x;
            }
            else
            {
                Father[x]=Find(Father[x]);
                return Father[x];
            }
        }
        void Merge(int x,int y)
        {
            int ax=Find(x),ay=Find(y);
            if (Cnt[ax]<Cnt[ay])//小的接到大的上
            {
                Cnt[ay]+=Cnt[ax];
                Father[ax]=ay;
            }
            else
            {
                Cnt[ax]+=Cnt[ay];
                Father[ay]=ax;
            }
        }
};

持续更新中。。。

并查集 笔记

before 正片

（最基础的）正片

正片的优化

相关推荐