听起来玄乎，其实比较朴素的东西。
扩展域并查集是用来处理染色判定问题的一种工具。具体来说，对于一些问题，我们可能需要将一个图划分为一些不交的点集，然后保证这些点集内部的点之间没有互相连边。
一个典型的例子是二分图。事实上，一般而言扩展域并查集都只是用来做二分图的判定而已。
还是以判断图是否是二分图为例。其做法是将每个点 \(u\) 拆成黑点和白点，我们设其编号分别为 \(u,u+n\)，图上每有一条边 \((u,v)\)，我们就在并查集上连 \((u,v+n),(u+n,v)\) 两条边，也就是白点和黑点互相连边。
最后的判定是，如果有点 \(u,u+n\) 即表示同一个点的黑白点在同一个连通块内则不是二分图，否则是。
正确性证明比较显然，连边的过程实际上就是在做黑白染色的过程。这里的黑白染色是指如果一个点是白色，那么与其相邻的所有点都会是黑色，反之亦然。从任意点开始染色都能够构造出一个合法的黑白染色方案显然是二分图合法的充要条件。
具体的含义也就是钦定当前点是白点，与其有连边的点的形态是什么样，钦定当前点是黑点，与其有连边的点的形态又是什么。黑白点在同一个连通块内就表示着钦定当前点是白点，黑白染色后当前点又会被染成黑点，这就意味着矛盾也就是不能通过黑白交替染色也就是图不是二分图。
通过这样的过程我们大概也能感知到为什么这个不是很好做多集合划分的问题。假设原图要划分为 \(k\) 个集合，那么显然每个点就要拆成 \(k\) 个颜色，于是每一次查询与合并都至少会达到 \(O(k^2\alpha(n))\) 的复杂度，空间也会变成 \(O(kn)\)。
code
下面给出一个可撤销的扩展域并查集，通过启发式合并能够做到 \(O(\log n)\) 查询与合并，\(O(1)\) 撤销。其中如果 \(cnt\) 恰为 0 代表当前图仍然是二分图，否则不是。
点击查看代码
namespace uni{int fa[N<<1],siz[N<<1],cnt=0,top=0;pii stk[N<<1];void init(){for(int i=1;i<=n<<1;i++)fa[i]=i,siz[i]=1;}int find(int x){return fa[x]==x?x:find(fa[x]);} int oth(int x){return x>n?x-n:x+n;}void merge(int x,int y){x=find(x),y=find(y);if(x==y){return;}if(siz[x]>siz[y])swap(x,y);stk[++top]={y,x}; //x 连向 yfa[x]=y;siz[y]+=siz[x];cnt+=(find(x)==find(oth(x)))+(find(y)==find(oth(y)));}void split(){ //去掉栈顶的连边int y=stk[top].first,x=stk[top].second;siz[y]-=siz[x];fa[x]=x;top--;}
}