Yurchiu's Blog
Yurchiu
An AFO whker.
  首页
  归档
158
  标签
81
  分类
24
  说说
  关于
  留言
  链接
  设置

并查集 2

Yurchiu 2021-02-22, 09:34:42 3.4k 隐藏左右两栏 展示左右两栏
首页 / 并查集 2

本文主要以题解为主。以“关押罪犯”为例介绍并查集的用法。

P1525 [NOIP2010 提高组] 关押罪犯

2×1042\times 10^4 个罪犯，10510^5 个仇恨关系，使用分在两个监狱的方式，使得最大仇恨值最小。

题解

二分答案+二分染色

似乎和并查集无关呢。

单调性分析：屏蔽的边越多，越容易交替染色，反之越难交替染色成功（类似二分图染色）。

对边权排个序，进行二分，染色时若当前边权大于等于 mid 才继续染色。

若染色成功，更新答案。

代码见命名空间 2。

并查集法（适用范围小）

贪心，对边权从大到小排序，枚举边时第一个矛盾不可调和的边的权即为题目所求。若根据前面的关系，x 和 y 在同一集合（是朋友），而当前边连接了 x 和 y（x 和 y 是敌人），则此矛盾不可调和。

枚举边时，使用一个数组 enemy[] 记录每个人的敌人。如果已记录，直接合并 x 和 enemy[y] ，以及 y 和 enemy[x]（敌人的敌人即是我的朋友）。

代码见命名空间 3。

扩展域并查集

扩展域并查集可以维护多组关系，适用于有多组关系需要用并查集维护的题目，并且可以不用推像带权并查集那样繁琐的式子。其主要思想是将一个点拆分成好几个点来维护多组关系。

这类题目只要找准题目中有几组关系，把握住，我的敌人的敌人就是我的朋友的原则（大部分题满足，可能有少部分题不满足这个原则，注意分析）。

本题目可设置两个域。一个表示“朋友”关系，另一个表示“敌人”关系。

仍按贪心法枚举。每次合并 x 和 y 的敌人域 ，以及 y 和 x 的敌人域。

“敌人域”的实现：设 x 和 x+n 是敌人，那么 x+n 和 y 就是朋友了。

代码见命名空间 1。

带权并查集

并查集的边加入权以维护集合间的关系。

我们让并查集中，若两点距离为偶数，则两点是朋友；若两点距离为奇数，则两点是敌人。

如图，以 1 为参照，1 和 2 为朋友，1 和 4 敌对，1 和 3 为朋友。

现在，要解决合并的问题。

如图，以 1 为参照（根节点），现在要将 4 所在集合合并到 2 所在集合上（3 是 4 的祖先）。若使 2 和 4 为敌人（合并 2 和 4），如何处理？

我们设一个点距离父亲的距离为 dis[i]。要使 2 和 4 为敌人，则合并后的 2 到根节点的距离和 4 到根节点的距离必定奇偶性不同。我们在合并时要求 dis[3]。

根据以上我们可以得到：dis[2]=dis[3]+dis[4]+1（加一减一无所谓）。移一下项得：dis[3]=dis[4]-dis[2]-1。这个过程在合并中处理。

还有路径压缩的问题。若使用递归写法，我们可以在递归返回途中，对 dis 值进行更新（累加 & 取模）。

代码见命名空间 4。

代码

点击查看
#include<bits/stdc++.h>
using namespace std;
namespace _yz1//扩展域并查集
{
	const int N=20000+10,M=100000+10;
	int n,m,dad[N*2];
	struct edge{int fir,sec,len;}e[M];
	bool cmp(edge x,edge y){return x.len>y.len;}
	void start(int n)
	{
    	for(int i=1;i<=n;i++)
       		dad[i]=i;
   		return;
	}
	int find(int x)
	{   
    	while(x!=dad[x])
        	x=dad[x]=dad[dad[x]];
    	return x;
	}
	void union_(int x,int y)
	{
    	int d1=find(x),d2=find(y);
    	dad[d1]=d2;
    	return;
	}
	void yzmain()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
			scanf("%d%d%d",&e[i].fir,&e[i].sec,&e[i].len);
		sort(e+1,e+1+m,cmp);start(n*2);
		for(int i=1;i<=m;i++)
		{
			int d1=e[i].fir,d2=e[i].sec;
			if(find(d1)==find(d2)) {printf("%d\n",e[i].len);return;}
			else {
				union_(d1,d2+n);
				union_(d2,d1+n);
			}
		}
		printf("0\n");
		return;
	}
}
namespace _yz2//二分图染色+二分答案
{
	const int N=20000+10,M=100000+10;
	struct edge{int nxt,to,len;}e[M*2];
	int n,m,head[N],cnt=0,ans,v[N],val[M];
	void add(int x,int y,int len){e[++cnt]=(edge){head[x],y,len};head[x]=cnt;}
	int dfs(int now,int color,int con)
	{
		int ret=0;
		if(v[now]!=-1 && color!=v[now]) return 1;
		else if(v[now]!=-1 && color==v[now]) return 0;
		v[now]=color;
		for(int i=head[now];i;i=e[i].nxt)
		{
			int to=e[i].to;
			if(e[i].len>con)  ret=max(dfs(to,color^1,con),ret);
		}
		return ret;
	}
	int check(int mid)
	{
		int ret=0;
		memset(v,-1,sizeof(v));
		for(int i=1;i<=n;i++)
			if(v[i]==-1) ret=max(dfs(i,1,mid),ret);
		return ret;
	}
	void yzmain()
	{
		int t1,t2,t3,l=0,r,mid;
		scanf("%d%d",&n,&m);r=m;
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&t1,&t2,&t3);
			add(t1,t2,t3);
			add(t2,t1,t3);
			val[++val[m+5]]=t3;
		}
		sort(val+1,val+1+m);
		while(l<=r)
		{
			mid=(l+r)/2;
			if(check(val[mid])) l=mid+1;
			else ans=val[mid],r=mid-1;
		}
		printf("%d",ans);
		return;
	}
}
namespace _yz3//并查集
{
	const int N=20000+10,M=100000+10;
	int n,m,dad[N],enemy[N];
	struct edge{int fir,sec,len;}e[M];
	bool cmp(edge x,edge y){return x.len>y.len;}
	void start(int n)
	{
    	for(int i=1;i<=n;i++)
       		dad[i]=i;
   		return;
	}
	int find(int x)
	{   
    	while(x!=dad[x])
        	x=dad[x]=dad[dad[x]];
    	return x;
	}
	void union_(int x,int y)
	{
    	int d1=find(x),d2=find(y);
    	dad[d1]=d2;
    	return;
	}
	void yzmain()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
			scanf("%d%d%d",&e[i].fir,&e[i].sec,&e[i].len);
		sort(e+1,e+1+m,cmp);start(n);
		for(int i=1;i<=m;i++)
		{
			int d1=e[i].fir,d2=e[i].sec;
			if(find(d1)==find(d2)) {printf("%d\n",e[i].len);return;}
			else {
				if(!enemy[d2]) enemy[d2]=d1; else union_(d1,enemy[d2]);
				if(!enemy[d1]) enemy[d1]=d2; else union_(d2,enemy[d1]);
			}
		}
		printf("0\n");
		return;
	}
}
namespace _yz4//带权并查集
{
	const int N=20000+10,M=100000+10;
	int n,m,dad[N],dis[N];
	struct edge{int fir,sec,len;}e[M];
	bool cmp(edge x,edge y){return x.len>y.len;}
	void start(int n)
	{
    	for(int i=1;i<=n;i++)
       		dad[i]=i;
   		return;
	}
	int find(int x)
	{
		int ret;//注意细节。
   		if(dad[x]==x)
        	return dad[x];
		ret=find(dad[x]);
		dis[x]=(dis[x]+dis[dad[x]])%2;
    	return dad[x]=ret;
	}
	void union_(int x,int y)
	{
    	int d1=find(x),d2=find(y);
		dis[d1]=((dis[x]-dis[y]-1)%2+2)%2;//将 dis 值变为在模 2 意义下最小的非负整数。
    	dad[d1]=d2;
		return;
	}
	void yzmain()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
			scanf("%d%d%d",&e[i].fir,&e[i].sec,&e[i].len);
		sort(e+1,e+1+m,cmp);start(n);
		for(int i=1;i<=m;i++)
		{
			int d1=e[i].fir,d2=e[i].sec;
			if(find(d1)==find(d2) && dis[d1]%2==dis[d2]%2)
			{//一定注意 if 判断中的语句先后问题。先 find 保证后面的 dis 的值成为了一个点到根节点的距离。
				printf("%d\n",e[i].len);
				return;
			}
			union_(d1,d2);	
		}
		printf("0\n");
		return;
	}
}

int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yzCE::yzmain();
	return 0;
}

其他题目

P2024 [NOI2001] 食物链

题意

动物王国中有三类动物 A，B，C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。

现有 NN 个动物，以 1−N1-N 编号。每个动物都是 A，B，C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 NN 个动物所构成的食物链关系进行描述：

  • 第一种说法是 1 X Y，表示 XX 和 YY 是同类。
  • 第二种说法是 2 X Y，表示 XX 吃 YY。

此人对 NN 个动物，用上述两种说法，一句接一句地说出 KK 句话，这 KK 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

  • 当前的话与前面的某些真的话冲突，就是假话
  • 当前的话中 XX 或 YY 比 NN 大，就是假话
  • 当前的话表示 XX 吃 XX，就是假话

你的任务是根据给定的 NN 和 KK 句话，输出假话的总数。

1≤N≤5×1041\le N\le 5\times10^4，1≤K≤1051\le K\le 10^5。

点击查看题解

题解

扩展域并查集

本题目可设置三个域。代码见命名空间 1，详情见注释。

带权并查集

我们设两点之间的距离  mod 3\bmod 3 的值是被吃关系（仍以根节点为参照；x 的距离比 y 的距离大 11，则 x 吃 y ）。

仍和上题情况一样：

  • 2 和 4 同种：dis2≡dis3+dis4(mod3)dis_2 \equiv dis_3+dis_4 \pmod3。
  • 2 吃 4：dis2≡dis3+dis4+1(mod3)dis_2 \equiv dis_3+dis_4+1 \pmod3。

移一下项即可。代码见命名空间 2，详情见注释。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz1//扩展域并查集
{
	const int N=50000+10,M=100000+10;
	int n,m,dad[N*3],ans=0;
	void start(int n)
	{
    	for(int i=1;i<=n;i++)
       		dad[i]=i;
   		return;
	}
	int find(int x)
	{   
    	while(x!=dad[x])
        	x=dad[x]=dad[dad[x]];
    	return x;
	}
	void union_(int x,int y)
	{
    	int d1=find(x),d2=find(y);
    	dad[d1]=d2;
    	return;
	}	
	void yzmain()
	{
		int t1,t2,t3;
		scanf("%d%d",&n,&m);start(n*3);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&t1,&t2,&t3);
			if(t2>n || t3>n) {ans++;continue;}
			if(t1==1)
			{
				if(find(t2)==find(t3+n) || find(t2)==find(t3+n*2)) {ans++;continue;}
                //如果 t2 和 t3 不是同类，fAKe 数加一。
				union_(t2,t3);
				union_(t2+n,t3+n);
				union_(t2+2*n,t3+2*n);
			}
			else
			{
				if(find(t2)==find(t3) || find(t2)==find(t3+n*2)) {ans++;continue;}
                //如果 t2 和 t3 是同类，或 t3 反过来吃了 t2，fAKe 数加一。
				union_(t2,t3+n);
				union_(t2+n,t3+n*2);
				union_(t2+n*2,t3);
			}
		}
		printf("%d\n",ans);
		return;
	}
}
namespace _yz2//带权并查集
{
	const int N=50000+10,M=100000+10;
	int n,m,dad[N],dis[N],ans=0;
	int moder(int x){return (x%3+3)%3;}
	void start(int n)
	{
    	for(int i=1;i<=n;i++)
       		dad[i]=i;
   		return;
	}
    int find(int x)
    {
        int ret;
        if(dad[x]==x)
            return dad[x];
        ret=find(dad[x]);
        dis[x]=moder(dis[x]+dis[dad[x]]);
        return dad[x]=ret;
    }
	void yzmain()
	{
		int t1,t2,t3;
		scanf("%d%d",&n,&m);start(n);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&t1,&t2,&t3);
			if(t2>n || t3>n || (t1==2&&t2==t3)) {ans++;continue;}
			if(t1==1)
			{
				int d1=find(t2),d2=find(t3);
				if(d1==d2 && moder(dis[t2])!=moder(dis[t3])) {ans++;continue;}
                //如果 d1 和 d2 已合并过，且两者不同类，fAKe 数加一。
       			if(d1!=d2) dis[d1]=moder(dis[t3]-dis[t2]),dad[d1]=d2;
                //没被合并，计算 dis 值。
			}
			else
			{
				int d1=find(t2),d2=find(t3);
				if(d1==d2 && moder(dis[t2])!=moder(dis[t3]+1)) {ans++;continue;}
                //如果 d1 和 d2 已合并过，且两者吃的关系不对，fAKe 数加一。
        		if(d1!=d2) dis[d1]=moder(moder(dis[t3]+1)-moder(dis[t2])),dad[d1]=d2;
                //没被合并，计算 dis 值。
			}
		}
		printf("%d\n",ans);
		return;
	}
}

int main()
{
    //freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yzCE::yzmain();
	return 0;
}

P1197 [JSOI2008]星球大战

题意

无向图，4×1054\times10^5 个点，2×1052\times10^5 条边，顺次删去点，顺次统计连通块个数。

点击查看题解

题解

既然按顺次不好解决，我们可以使用逆向思维，使用离线算法。

我们用邻接表和并查集来维护。先把图建好，并查集合并时把被摧毁的星球屏蔽掉，得到连通块数 total。这是要输出的最后一个答案。

再逆向一个个恢复星球。每回复一个时，total 首先要加一（星球本身是连通块）。按照建的图，对这个点所相连的点尝试并查集合并。若合并成功（两者不属于同一集合且另一个星球是没被摧毁的），连通块个数减一。

存下答案，再逆向输出答案即可。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=400000+10;
	struct edge{int nxt,to;}e[N];
	int head[N],cnt=0,n,m,k,dead[N],dstar[N],ans[N],dad[N],total=0;
	int ta[N],tb[N];
	void add(int x,int y){e[++cnt]=(edge){head[x],y};head[x]=cnt;}
	void start(int n)
	{
    	for(int i=1;i<=n;i++)
       		dad[i]=i;
   		return;
	}
	int find(int x)
	{   
    	while(x!=dad[x])
        	x=dad[x]=dad[dad[x]];
    	return x;
	}
	void union_(int x,int y)
	{
    	int d1=find(x),d2=find(y);
    	dad[d1]=d2;
    	return;
	}	
	int getans()
	{
		int ret=0;
		for(int i=0;i<=n-1;i++)
			if(dad[i]==i && dead[i]!=1) ret++;
		return ret;
	}
	void yzmain()
	{
		int ta,tb;
		scanf("%d%d",&n,&m);start(n);
		for(int i=1;i<=m;i++) 
			scanf("%d%d",&ta,&tb),add(ta,tb),add(tb,ta);
		scanf("%d",&k);
		for(int i=1;i<=k;i++) scanf("%d",dstar+i),dead[dstar[i]]=1;
		for(int i=0;i<=n-1;i++)
		{
			if(dead[i]) continue;
			for(int j=head[i];j;j=e[j].nxt)
				if(!dead[e[j].to])
					union_(e[j].to,i);
		}
		total=ans[k]=getans();
		for(int i=k;i>=1;i--)
		{
			total++;
			for(int j=head[dstar[i]];j;j=e[j].nxt)
			{
				int to=e[j].to;
				if(find(dstar[i])!=find(to) && dead[to]!=1)
					union_(dstar[i],to),total--;
			}
			ans[i-1]=total;
			dead[dstar[i]]=0;
		}
		for(int i=0;i<=k;i++)
			printf("%d\n",ans[i]);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}



本文作者：Yurchiu

本文链接：https://yz-hs.github.io/fb7ca72a2695/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。


OI 二分 图论 并查集 离线算法 二分答案
最后更新：2023-08-21, 23:18:21
By Yurchiu.
最近更新旧文更新
[Works] 自白 终章
《幽默报 10》
AFO 有感
OI 之旅
《幽默报》
[Works] 自白
[Idea] 试卷排序
其他物件杂物收纳
Hitokoto

Yurchiu 说，除了她以外的人都很强！嘤嘤嘤~~
博客信息
文章数目
158
最近更新
08-21
本站字数
350.6k
文章目录

©2019-2023 Yurchiu. All rights reserved.

Theme Cutie, by Yurchiu.