并查集相关

按秩合并

顾名思义，就是按一些优先级合并，这个优先级，在这里被称为秩。

秩的严格定义：一棵子树的最大深度\(/\)一棵子树的大小。

这里我们约定一棵子树的秩，是它的最大深度。我们总会将秩小的节点 \(x\) 合并到秩大的节点 \(y\) 上。这样做，是为了令整棵树尽可能平衡：不会出现某些深度很大的节点。于是时间复杂度被均摊为 \(O(\log n)\)。

也可约定一棵子树的秩，是它的大小。我们仍然将秩小的节点 \(x\) 合并到秩大的节点 \(y\) 上。对于 \(x\) 而言，其每个点增加了 \(1\) 的查询代价，总共增加了 \(size_x\) 的查询代价，我们自然希望令增加的查询代价最小，于是得证。

按秩合并在一般情况下时间复杂度远没有路径压缩优秀，但它的优点是保留了原有的结构，能够进行撤销。这在一些题目上是非常好的性质。

下面来看一道题目。

[BZOJ4668]冷战

• 有 \(N\) 个点，\(M\) 次操作，强制在线。
• 操作 \(1\)：在两个点 \(x,y\) 之间连一条边
• 操作 \(2\)：询问最早加入的令 \(x,y\) 连通的边，如果不存在则输出 \(0\)

\(\text{BZOJ}\) 已经挂了，应该都知道 \(\text{darkbzoj}\) 吧（战术后仰

如果只是询问连通性，常规的路径压缩就可胜任。但是我们需要知道何时在加入 \(u,v\) 这条边恰好 \(x,y\) 恰好连通，这就要求在并查集上保留合并时的结构。

自然想到按秩合并。\(x,y\) 连通，在并查集的结构上就体现为 \(x,y\) 之间有一条路径。那么我们只需要对于每条边以连边的时间为边权，答案就是 \(x,y\) 路径上的最大边权。

这个东西可以暴力询问，因为在以树的最大深度为秩时，深度是有保证的，这也就体现出了按秩合并的优越性。

放一下代码，写的很随便，看看就好（

#include<cstdio>
int rnk[500005],val[500005],fa[500005],vis[500005];
inline int read() {
	register int x=0,f=1;register char s=getchar();
	while(s>‘9‘||s<‘0‘) {if(s==‘-‘) f=-1;s=getchar();}
	while(s>=‘0‘&&s<=‘9‘) {x=x*10+s-‘0‘;s=getchar();}
	return x*f;
}
inline int max(const int &x,const int &y) {return x>y? x:y;}
inline int find(int x) {while(fa[x]!=x) x=fa[x]; return x;}
int main() {
	int n=read(),m=read(),ans=0,now=0;
	for(register int i=1;i<=n;++i) fa[i]=i;
	for(register int i=1;i<=m;++i) {
		int op=read(),u=read(),v=read();
		u^=ans;v^=ans; 
		if(op==0) {
			++now;
			int fx=find(u),fy=find(v);
			if(fx!=fy) {
				if(rnk[fx]<rnk[fy]) {fa[fx]=fy;val[fx]=now;}
				else if(rnk[fx]>rnk[fy]) {fa[fy]=fx;val[fy]=now;}
				else {fa[fx]=fy;val[fx]=now;++rnk[fy];}
			}
		}
		else {
			int res=0;
			if(find(u)!=find(v)) {printf("%d\n",ans=0);}
			else {
				int x=u,aim,maxt=0;
				while(x!=fa[x]) {vis[x]=1;x=fa[x];} x=v;
				while(!vis[x]&&x!=fa[x]) {x=fa[x];} aim=x; x=u;
				while(x!=aim) {maxt=max(maxt,val[x]);x=fa[x];} x=v;
				while(x!=aim) {maxt=max(maxt,val[x]);x=fa[x];} x=u;
				while(x!=fa[x]) {vis[x]=0;x=fa[x];}
				printf("%d\n",ans=maxt);
			}
		}
	}
}

并查集相关

原文：https://www.cnblogs.com/tommy0103/p/13749379.html