【模板】并查集 DSU

posted on 2021-09-12 15:49:52 | under 模板 | source

0x00 模板

并查集维护的是这样一个问题：

\(n\) 个点，初始时每个点自己一个集合。

• \({\tt merge}(x,y)\)：合并 \(x,y\) 所在集合。
• \({\tt query}(x,y)\)：询问 \(x,y\) 是否在同一个集合中。

把每个集合看作一棵有根树，记 \(fa_x\) 为 \(x\) 的父亲，添加操作 \({\tt find}(x)\) 为沿着 \(fa\) 往上爬到达的根结点。

对于 \(\tt merge\) 操作，找到 \(fx={\tt find}(x),fy={\tt find(y)}\)，把这两棵有根树合并，直接把 \(fx\) 连向 \(fy\) 做 \(fy\) 的儿子，反过来也行。

对于 \(\tt query\) 操作，如果 \({\tt find}(x)={\tt find}(y)\)，说明 \(x,y\) 所在有根树的根相同，即在同一棵有根树中，即在同一集合中。

写下来会发现 TLE，我们需要一些优化，两个角度：

• \({\tt find}(x)\) 时，如果这棵树变成一条链，我一直在跳链，有意义吗？可以用类似于记忆化的技巧，把链打成菊花，一步到位。
• \({\tt merge}(x)\) 时，如果我执着地把大树连到小树上，这不就成链了吗？考虑把小树连到大树上，发现每次跳 \(fa\) 子树大小至少翻倍（反证法），那么树高就是 \(O(\log n)\) 了。

Tarjan 告诉我们，第一种叫路径压缩，\(O(n\log n)\)；第二种叫启发式合并，\(O(n\log n)\)；如果两种一起用，复杂度降至 \(O(n\alpha(n))\)，其中 \(\alpha(n)\) 为反阿克曼函数，增长极慢，在 \(10^9\) 范围内可看作 \(4\)。于是我们有了一个优秀的并查集。

template<int N> struct dsu{
    int fa[N+10],siz[N+10],cnt;
    dsu(int n=N):cnt(n){for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;}
    int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    void merge(int x,int y){if(x=find(x),y=find(y),x!=y) siz[x]<siz[y]&&(swap(x,y),0),cnt--,fa[y]=x,siz[x]+=siz[y];}
};

0x01 区间染色

\(n\) 个点排成一列，一开始没被染色，支持操作：

• \({\tt assign}(l,r,k)\)：将 \([l,r]\) 的点染色成 \(k\)，已被染色的点忽略。
• \({\tt remain}(l,r)\)：询问 \([l,r]\) 内有没有未被染色的点。

修改 \(fa_x\) 的定义：\(x\) 右边（包括 \(x\)）第一个未被染色的点。显然初始时 \(fa_x=x\)。

考虑 \(\tt assign\) 操作，我们先找到 \({\tt find}(l)=l'\) 这个点没被染色，如果 \(l'\leq r\)，记录 \(c_{l'}=k\) 我们把 \(l'\) 染成了 \(k\)，根据定义我们应该修改 \(fa_{l'}\) 了，将它指向下一个未被染色的点，显然这个点是 \({\tt find}(l'+1)\)，然后迭代更新即可。

考虑 \(\tt remain\) 操作，定义，若 \({\tt find}(l)\leq r\) 就有剩下的点。

我们发现这些操作很像并查集的操作，可以直接套用，路径压缩也可以加，注意最好不要启发式合并，以免打乱顺序。

template<int N> struct exdsu:public dsu<N>{//展开
    int a[N+10];
    exdsu(){memset(a,0,sizeof a);}
    void assign(int l,int r,int k){while(l<=r) if(this->find(l)==l) a[l]=k,this->fa[l]=this->find(l+1); else l=this->find(l);}
    bool remain(int l,int r){return this->find(l)<=r;}
    int operator[](int i){return a[i];}
};
template<int N> struct exdsu:public dsu<N>{
    int a[N+10];
    exdsu(){memset(a,0,sizeof a);}
    void assign(int l,int r,int k){while((l=this->find(l))<=r) a[l]=k,this->merge(l,l+1);}
    bool remain(int l,int r){return this->find(l)<=r;}
    int operator[](int i){return a[i];}
};

继承

面向对象语言的特性，以 C++ 为例，格式为：

struct a{};
struct b:public a{};

在 C++ 中，struct 和 class 几乎相同，区别在于 struct 默认 public 而 class 默认 private，不过这不重要。

在 OI 中使用对象继承，可以把父类的变量、函数移植到新的子类，子类也有这些函数，可以在子类创建新的变量和函数。构造函数还要自己写，父子的都会调用。

为了过编译，父类的函数需要加 this->merge(x,y)，告诉编译器 merge 是父类的函数。OI 用到的继承可以到这停了。

话说整一下复杂度，\(O(n\log n)\)，每个点只染色一次，合并只有 \(O(n)\) 次，均摊 \(O(n)\)，\(\log\) 是并查集复杂度。

0x02 静态区间覆盖

\(n\) 个点排成一列，一开始没被染色，支持操作：

• \({\tt assign}(l,r,k)\)：将 \([l,r]\) 的点染色成 \(k\)，已被染色的点颜色被覆盖。

最后输出 \(n\) 个点的颜色。

每个点的颜色由它最后被染的颜色决定，倒着做上一题的覆盖操作就好了。