并查集

· · 算法·理论

<目录

并查集

并查集是一种只关心元素对于集合的所属关系的数据结构。
它的原型是一棵树，使用 “父亲表示法” 表示，用数组 Fa[i] 保存 i 的父亲的编号。
每个孩子都有一个父亲，而一个家族的祖先便是这个家族的标识。
如果你我有着同样的祖先，则你和我是一个家族的。
特别的，祖先的父亲是自己。

并查集善于添加关系。
如果涉及到破化关系，可以考虑反向建边。

\sf\hspace{5cm}-David \color{lightgray}\textsf{2023-1-31 Updated}

一般的并查集

初始化

先认为每个元素自成集合，即 Fa[i]=i ，并集的时候在把父亲设为目标集合的祖先。

找父亲

由于并查集只关心所属关系，所以我爸是你或你爸是我没什么区别。所以，我们在找祖先时可以做路径优化，就是忽略之前所有的父子关系，统一认为一个家族所有人都是这个家族祖先的直接孩子，包括祖先自己。
使用递归函数向上找父亲、祖父、曾祖父……
回溯的时候顺便把父亲的父亲设为找到的那个祖先。

int Find(int n)
{
    if(Fa[n]!=n)    Fa[n]=Find(Fa[n]);
    return Fa[n];
}

并集

只需要操作一下祖先即可。

void Merge(int a,int b)
{
    a=Find(a),b=Find(b);
    Fa[b]=a;
}

查集

如果你我有着同样的祖先，则你和我是一个家族的。

bool Judge(int a,int b)
{
    a=Find(a),b=Find(b);
    return (a==b);
}

拓展域并查集

有些时候，
我们不仅知道某些与某些在一个集合中，
我们还知道某些与某些不在一个集合中，
甚至知道某些和某些在相邻的两个集合中。

怎么办呢？
这个时候，我们就要请出“反我”了。
让我和“反我”始终不在一个集合之中，如果知道某某与我不在一个集合之中，就说明此某与“反我”在一个集合，我与“反此某”在同一集合中。
就巧妙地转化了问题。

封装一下？

正常并查集

template<int maxlength>
class DisjointSets
{
    private:
        int Fa[maxlength+5];
    public:
        DisjointSets()
        {
            for(int i=0;i<maxlength;i++)
                Fa[i]=i;
        }
        DisjointSets(DisjointSets<maxlength>&m)
        {
            for(int i=0;i<maxlength;i++)
                Fa[i]=m.Fa[i];
        }
        ~DisjointSets(){}
        int Find(int n)
        {
            if(n<0||n>=maxlength)
                return -1;
            if(Fa[n]!=n)
                Fa[n]=Find(Fa[n]);
            return Fa[n];
        }
        void Merge(int a,int b)
        {
            if(a<0||a>=maxlength||b<0||b>=maxlength)
                return;
            Fa[Find(b)]=Find(a);
            return;
        }
        bool Judge(int a,int b)
        {
            if(a<0||a>=maxlength||b<0||b>=maxlength)
                return false;
            return Find(a)==Find(b);
        }
        void operator=(DisjointSets m)
        {
            for(int i=0;i<maxlength;i++)
                Fa[i]=m.Fa[i];
        }
        int& operator[](int i){return Fa[i];}
};

拓展域并查集

template<int maxlength,int extent>
class ExjointSets
{
    private:
        int Fa[extent*maxlength+30];
        int get(int x,int y){return x*maxlength+y;}
        int find(int n)
        {
            if(Fa[n]!=n)
                Fa[n]=find(Fa[n]);
            return Fa[n];
        }
        void merge(int a,int b){Fa[find(b)]=find(a);return;}
        bool judge(int a,int b){return find(a)==find(b);}
    public:
        ExjointSets()
        {
            const int amount=extent*maxlength;
            for(int i=0;i<amount;i++)
                Fa[i]=i;
        }
        ExjointSets(ExjointSets<maxlength,extent>&m)
        {
            const int amount=extent*maxlength;
            for(int i=0;i<amount;i++)
                    Fa[i]=m.Fa[i];
        }
        ~ExjointSets(){}
        int Find(int n,int a)
        {
            if(n<0||n>=maxlength||a<0||a>=extent) 
                return -1;
            return find(get(a,n));
        }
        void Merge(int a,int b,int dif)
        {
            if(a<0||a>=maxlength||b<0||b>=maxlength)
                return;
            if(dif<0||dif>=extent)
                return;
            for(int i=0;i<extent;i++)
                merge(get(i,a),get((i+dif)%extent,b));
            return;
        }
        bool Judge(int a,int b,int dif)
        {
            if(a<0||a>=maxlength||b<0||b>=maxlength)
                return false;
            if(dif<0||dif>=extent)
                return false;
            return judge(get(0,a),get(dif,b));
        }
};