数据结构并查集

Akiyama_mzk · 2024-08-07 16:30:56 · 算法·理论

\texttt{part 1} 朴素的并查集

引入

并查集是一种用于管理元素所属集合的 数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

你需要写一个数据结构实现以下两种操作

1: 合并 x,y 所在的集合。

2: 询问 x y 是否处于同一个集合。

顾名思义，并查集支持两种操作：

合并 union：合并两个元素所属集合（合并对应的树）。

查询 find：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合。

但是，并查集无法以较低复杂度实现集合的分离。

初始化

初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。

for(int i=1;i<=n;i++){
    fa[i]=i;
}

查询

我们需要沿着树向上移动，直至找到根节点。

  return fa[x]==x?x:find(fa[x]);

合并

将一棵树连同根节点一块并到另一棵树上。

int uni(int x,int y){
    return fa[find(x)]=find(y)
}

\texttt{part 2} 路径压缩与按秩合并

路径压缩

查询过程中经过的每个元素都属于该集合，我们可以将其直接连到根节点以加快后续查询。

return fa[x]==x?x:fa[x]=find(fa[x]);

按秩合并

合并时，选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度。我们可以将节点较少或深度较小的树连到另一棵，以免发生退化。

如果只使用按秩合并，而不使用路径压缩，时间复杂度为 O(m\log n)。由于路径压缩单次合并可能造成大量修改，有时路径压缩并不适合使用。例如，在可持久化并查集、线段树分治 + 并查集中，一般使用只按秩合并的并查集。

int uni(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx==fy){
        return;
    }
    if(sized[fx]<sized[fy]){
        swap(x, y);
    }
    fa[fy]=fx;
    sized[x]+=sized[y];
}

复杂度

时间复杂度

\Theta(m\alpha(n)) 的证明。

空间复杂度

显然为 \Theta(n)。

\texttt{part 3} 带权并查集

我们还可以在并查集的边上定义某种权值、以及这种权值在路径压缩时产生的运算，从而解决更多的问题。

比如对于经典的 P1196 [NOI2002] 银河英雄传说。

我们可以用并查集实现，题目要求我们计算 i 和 j 之间的战舰数目 C_{ij}，我们仅靠朴素的并查集模板是无法解决的，自然要维护额外的信息。

数组 d_{x} 记录 x 到根节点的距离，即边的数目。 那么对于 C_{ij}，如果 i,j 在同一列，我们就应该输出 abs(d_{i}-d_{j})-1。

路径压缩时：

并查集记录子树的大小。考虑统计每次操作的贡献。如果第 i 次操作 a_i 和 b_i 分属于两个不同子树，就将这两个子树合并，并将两者子树大小的乘积乘上 i 累加到答案里。时间复杂度 O(n\alpha(n))。

杂题 2: 并查集生成树

题面

有 n 个点，初始时均为孤立点。

接下来有 m 次加边操作，第 i 次操作在 a_i 和 b_i 之间加一条无向边。

接下来有 q 次询问，第 i 次询问 u_i 和 v_i 最早在第几次操作后连通。

\texttt{solution}

考虑在并查集合并的时候记录并查集生成树，也就是说如果第 i 次操作 a_i 和 b_i 分属于两个不同子树，那么把 (a_i,b_i) 这条边纳入生成树中。边权是 i。那么查询就是询问 u 到 v 路径上边权的最大值，可以使用树链剖分的方法维护。时间复杂度 O(n\log n)。

杂题 3: 并查集离线

题面

有 n 个点，初始时均为孤立点。

接下来有 m 次加边操作，第 i 次操作在 a_i 和 b_i 之间加一条无向边。

接下来有 q 次询问，第 i 次询问第 x_i 个点在第 t_i 次操作后所在连通块的大小。

\texttt{solution}

离线算法：考虑将询问按 t_i 从小到大排序。在加边的过程中使用并查集顺便处理询问即可。时间复杂度 O(q\log q+(n+q)\alpha(n))。

杂题 4: 并查集与序列位置操作

题面

给一个长度为 n 的 01 序列 a_1,\ldots,a_n，一开始全是 0，接下来进行 m 次操作：

• 令 a_x=1

• 求 a_x,a_{x+1},\ldots,a_n 中左数第一个为 0 的位置。

\texttt{solution}

建立一个并查集，f_i 表示 a_i,a_{i+1},\ldots,a_n 中第一个 0 的位置。初始时 f_i=i。

对于一次 a_x=1 的操作，如果 a_x 原本就等于 1，就不管。否则我们令 f_x=f_{x+1}。

时间复杂度 O(n\log n)，如果要使用按秩合并的话实现会较为麻烦，不过仍然可行。也就是说时间复杂度或为 O(n\alpha(n))。

杂题 5: 并查集联通块与序列操作

题面

给出三个长度为 n 的正整数序列 a,b,c。枚举 1\le i\le j\le n，求 a_i\cdot b_j\cdot \min_{i\le k\le j}c_k 的最大值。

\texttt{solution}

按权值从大到小考虑 c_k。相当于我们在 k 上加入一个点，然后将 k-1 和 k+1 位置上的点所在的连通块与之合并（如果这两个位置上有点的话）。连通块上记录 a 的最大值和 b 的最大值，即可在合并的时候更新答案。时间复杂度 O(n\log n)。

杂题 6: 并查集与双联通分量

题面

给出一棵 n 个点的树，接下来有 m 次操作：

加一条从 a_i 到 b_i 的边。 询问两个点 u_i 和 v_i 之间是否有至少两条边不相交的路径。

\texttt{solution}

询问可以转化为：求 u_i 和 v_i 是否在同一个简单环上。按照双连通分量缩点的想法，每次我们在 a_i 和 b_i 间加一条边，就可以把 a_i 到 b_i 树上路径的点缩到一起。如果两条边 (a_i,b_i) 和 (a_j,b_j) 对应的树上路径有交，那么这两条边就会被缩到一起。

换言之，加边操作可以理解为，将 a_i 到 b_i 树上路径的边覆盖一次。而询问就转化为了：判断 u_i 到 v_i 路径上是否存在未被覆盖的边。如果不存在，那么 u_i 和 v_i 就属于同一个双连通分量，也就属于同一个简单环。

考虑使用并查集维护。给树定根，设 f_i 表示 i 到根的路径中第一个未被覆盖的边。那么每次加边操作，我们就暴力跳并查集。覆盖了一条边后，将这条边对应结点的 f 与父节点合并。这样，每条边至多被覆盖一次，总复杂度 O(n\log n)。使用按秩合并的并查集同样可以做到 O(n\alpha(n))。

杂题 7: 并查集与缩点与桥

题面

无向图 G 有 n 个点，初始时均为孤立点（即没有边）。

接下来有 m 次加边操作，第 i 次操作在 a_i 和 b_i 之间加一条无向边。

每次操作后，你均需要求出图中桥的个数。

桥的定义为：对于一条 G 中的边 (x,y)，如果删掉它会使得连通块数量增加，则 (x,y) 被称作桥。

强制在线。

\texttt{solution}

考虑用并查集维护连通情况。对于边双树，考虑维护有根树，设 p_i 表示结点 i 的父亲。也就是不带路径压缩的并查集。

如果第 i 次操作 a_i 和 b_i 属于同一个连通块，那么我们就需要将边双树上 a_i 到 b_i 路径上的点缩起来。这可以用并查集维护。每次缩点，边双连通分量的个数减少 1，最多减少 n-1 次，因此缩点部分的并查集复杂度是 O(n\alpha(n))。

为了缩点，我们要先求出 a_i 和 b_i 在边双树上的 \operatorname{LCA}。对此我们可以维护一个标记数组。然后从 a_i 和 b_i 开始轮流沿着祖先一个一个往上跳，并标记沿途经过的点。一但跳到了某个之前就被标记过的点，那么这个点就是 a_i 和 b_i 的 \operatorname{LCA}。这个算法的复杂度与 a_i 到 b_i 的路径长度是线性相关的，可以接受。

如果 a_i 和 b_i 分属于两个不同连通块，那么我们将这两个连通块合并，并且桥的数量加 1。此时我们需要将两个点所在的边双树连起来，也就是加一条 a_i 到 b_i 的边。因此我们需要将其中一棵树重新定根，然后接到另一棵树上。这里运用启发式合并，这样的总复杂度是 O(n\log n) 的。

综上，该算法的总复杂度是 O(n\log n+m\log n) 的。

\texttt{part 6} 可撤销并查集

可撤销并查集是一种扩展了标准并查集数据结构的数据结构，它允许在进行 union 和查询 find 操作的同时，能够 undo 或者撤销之前的操作。

这种数据结构通常用于支持一些需要回滚操作的应用，比如在离线算法中或者需要进行回退的决策问题中。

当然主要是应用于在线算法，因为离线算法反悔可以完全输入后在一起处理。

你需要写一个数据结构实现以下三种操作

1: 连接 x,y 。

2: 询问 x 与 y 是否连通 。

3: 撤回操作。

因为会破坏树形结构，导致在撤销操作时无法准确找到原始的父节点，不可以使用路径压缩来优化并查集。

当然，启发式合并或者按秩合并这两种合并方式对于并查集来说是没有用影响的。

因此，用栈来记录每次合并的操作，然后进行对 fa,size 等变量的维护即可。

算法原理：

• 查找

由于支持撤销操作，那么肯定不能路径压缩，否则会破坏树形结构，反悔时无法找到原本的父节点。

• 合并

既然不能路径压缩，我们要尽可能地减少树的深度。于是启发式合并 (或按秩合并)。

• 撤销

用栈来记录每次合并的操作。

用一个 stack，每次的操作往里放，先进去的会被晚撤销，撤销的一定是最近的这一步。

用 undo-sized，记录树的深度，undo-fa，记录它的父亲。

stack<pair<int*,int>> st;
int fa[],rnk[];
void init(int n){
    for(int i=0;i<=n;i++){
        fa[i]=i;
        rnk[i]=0;
    } 
}
int find(int x){
    if(x==fa[x]){
        return x;
    }
    return find(fa[x]);
}
void uni(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y){
        return;
    }
    if(rnk[x]<=rnk[y]){
        st.push({fa+x,fa[x]});
        fa[x]=y;
        if(rnk[x]==rnk[y]){
            st.push({rnk+y,rnk[y]});
            rnk[y]++;
        }
    }
    else{
        st.push({fa+y,fa[y]});
        fa[y]=x;
    }
}
void undo(){
    *stk.top().first=st.top().second;
    stk.pop();
}

\texttt{part 7} 可删除并查集

你需要写一个数据结构实现以下三种操作

1: 合并 x,y 所在的集合。

2: 把 x 移到 y 所在的集合。

3: 求 x 所在集合元素个数与元素和。

我们并不可以通过 uni 操作直接将 x 添加到 y 所在的集合。

因为如果我们直接

fa[find(x)]=find(y)

的话，x 的子节点也会与 x 一同并入 y 的集合。

我们可以通过给每个元素设置一个虚拟父节点，每次移动的时候操作的是实际的节点，而不是父节点即可完成。

因为这个时候操作的节点都是叶子节点，不会有副作用。

如果 x 点没有儿子就可以直接做。然后发现不管是 1 的合并还是 2 的直接移动都是直接接在根上的。

换言之只要每个集合的根节点不可能作为 x 点出现那么每次 2 操作就可以直接移动。

但是题目中 x 可以是 的任何一个点。因此你的集合的根节点不应该是 1\dots n 的任何一个点。对于每个集合的根，都应该是一个虚点。

方便起见我们把这 n 个虚点设置成了 i+n 的形式。

\texttt{part 8} 可持久化并查集

引入

你需要写一个数据结构实现以下三种操作

1: 合并 x,y 所在的集合。

2: 回到第 k 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态；。

3: 询问 x 与 y 是否在同一个集合内。

可持久化并查集是建立在可持久化数组上的，在学习可持久化并查集之前，需要先学习可持久化权值线段树，权值线段树。

众所周知，并查集有两种优化方式：

• 路径压缩

• 按秩合并

我们的并查集的 fa 数组是要用可持久化数组来维护的，那么路径压缩基本就不要考虑了。

return fa[x]==x?x:fa[x]=find(fa[x]);

每递归一次，只要进入 if 语句，fa 数组就会有一个位置被修改。

对于建立在主席树上的可持久化数组，每进行一次单点修改就会多一个新的版本存放新的结点。

会导致 MLE， 所以不要使用路径压缩。

因为每个版本的并查集的结点深度可能是不一样的，所以我们还需要要新开一个可持久化数组来记录每个版本的 dep 数组。

算法内容

对于操作 2，我们可以很容易的使用可持久化数组来实现。就直接把当前版本的根节点定为第 k 个版本的根节点就行了。

对于操作 1，也就是上面所说的按秩合并。对于操作 3，也就是在可持久化数组中查询。

#include<bits/stdc++.h>
using namespace std;
inline long long read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
    x=(x<<1)+(x<<3)+ch-'0';
    ch=getchar();
}
    return x*f;
}
void write(long long x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
int n,m,root[1000001],dfn,cnt;
struct union_set{
    struct node{
        int lson,rson,fa,dep;
    }t[8000001];
    int build(int l,int r){
        int x=++cnt;
        if(l==r){
            t[x].fa=l;
            return x;
        }
        int mid=(l+r)>>1;
        t[x].lson=build(l,mid);
        t[x].rson=build(mid+1,r);
        return x;
    }
    int update(int id,int l,int r,int x){
        if(l==r){
            return id;
        }
        int mid=(l+r)>>1;
        if(x<=mid){
            return update(t[id].lson,l,mid,x);
        }
        else{
            return update(t[id].rson,mid+1,r,x);
        }
    }
    int find(int x,int pre){
        int fa=update(root[x],1,n,pre);
        if(t[fa].fa==pre){
            return fa;
        }
        return find(x,t[fa].fa);
    }
    int build(int x){
        int id=++cnt;
        t[id]=t[x];
        return id;
    }
    int uni(int id,int l,int r,int x,int fa){
        int to=build(id);
        if(l==r){
            t[to].fa=fa;
            return to;
        }
        int mid=(l+r)>>1;
        if(x<=mid){
            t[to].lson=uni(t[id].lson,l,mid,x,fa);
        }
        else{
            t[to].rson=uni(t[id].rson,mid+1,r,x,fa);
        }
        return to;
    }
    int add(int id,int l,int r,int x){
        int to=build(id);
        if(l==r){
            t[to].dep++;
            return to; 
        }
        int mid=(l+r)>>1;
        if(x<=mid){
            t[to].lson=add(t[id].lson,l,mid,x);
        }
        else{
            t[to].rson=add(t[id].rson,mid+1,r,x);
        }
        return to;
    }
    void merge(int x,int l,int r){
        root[x]=root[x-1];
        l=find(x,l);
        r=find(x,r);
        if(t[l].fa!=t[r].fa){
            if(t[l].dep>=t[r].dep){
                swap(l,r);
            }
            root[x]=uni(root[x-1],1,n,t[l].fa,t[r].fa);
            if(t[l].dep==t[r].dep){
                root[x]=add(root[x],1,n,t[r].fa);
            }
        }
    }
    int same(int x,int l,int r){
        l=find(x,l);
        r=find(x,r);
        if(t[l].fa==t[r].fa){
            return 1;
        }
        else{
            return 0;
        }
    }
}tree;
int op,x,y;
signed main(){
    n=read();
    m=read();
    root[0]=tree.build(1,n);
    for(int i=1;i<=m;i++){
        op=read();
        if(op==1){
            x=read();
            y=read();
            tree.merge(i,x,y);
        }
        if(op==2){
            x=read();
            root[i]=root[x];
        }
        if(op==3){
            x=read();
            y=read();
            write(tree.same(i-1,x,y));
            printf("\n");
            root[i]=root[i-1];
        }
    }
    return 0;
}