自动搬运

查看原文

来自洛谷，原作者为

	huangziqin 自己选的路，跪着也要走完。||信息学爱好者||AFO

搬运于2025-08-24 22:57:08，当前版本为作者最后更新于2024-04-17 19:58:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题目挺巧妙的 。

首先考虑什么情况下不能确定电脑的情况 。

+ 1 2
+ 1 3
+ 2 4
+ 3 5

形如这样的样例是无法确定具体的电脑给了谁 。 明显地 ， 这组样例中人与人的状态连边形成了一棵树 。 同时 ， 我们也能确定这个连通块中有且仅有一个人没有电脑 ， 但是不能确定这个人具体是谁 ， 所以无法确定每个人的状态。

再以此为基础考虑一下什么情况下可以确定每个人都有电脑 。

注意到这句话 ： “电脑被送到了目前还没有电脑的居民手中 。” 所以如果出现了一个环 ， 则一定能确定这个环所在的连通块中每个人都有电脑 。

简单证明一下 ， 如果大小为 $n$ 的连通块中有 $n$ 条边 （ 出现环的充要条件 ）， 这意味着这 $n$ 个人被送了 $n$ 台电脑 ， 且每个人至多有一台电脑 ， 则每个人都有且仅有一台电脑 ， 得证。

再考虑一下电脑损坏的情况。

对于一个树形的连通块 ， 如果某个人的电脑损坏一定意味着他有过电脑 ， 分两种情况讨论一下：

1. $n=2$ 则我们一定能确定另一个人没有电脑 。
2. $n>2$ 则我们仍然不能确定这个连通块中哪一个人没有电脑 。

所以我们只用考虑这两种 corner case 即可 。

同时 ， 这个电脑被损坏的人又回到了原先的初始状态 ， 即与其他人没有连边 ， 本身没有电脑的情况 。

最后考虑回答 。

考虑该点所在的连通块状态 。

• 如果他是一个独立的点 （ 且没有自环 ） ， 则他一定没有电脑 。
• 如果他属于某个 $n>1$ 的连通块且其内部有环 ， 则他一定有电脑 。
• 如果他属于某个 $n>1$ 的树状连通块 ， 则他不能确定是否拥有电脑 。

代码实现细节

综上 ， 我们需要维护这些操作 ：

1. 连通块之间的合并
2. 查找连通块内是否有环
3. 分裂出某一个点
4. 查找连通块状态

通过 1,2 两个操作可以非常敏锐地发现我们的算法 并查集 。

所以关键在于 3 操作如何维护 。

因为并查集的删除非常麻烦 ， 所以我们考虑不删除的做法 。

因为发现被删除的点即使留在联通块内也对答案没有任何影响 。

所以不妨对于每个人维护一个 id 代表这个人对应着 id 这个点 ， 每次删除只需要增加新的 id 并且把人对应这个新的 id 即可 。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=13e5+7;
int n,m,f[N],id[N],cnt,x,sz[N],zt[N],y;
char opt;
//zt[]： 连通块的状态
int getf(int x)
{
	if(f[x]==x) return f[x];
	else return f[x]=getf(f[x]);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n+m;i++) f[i]=i;//并查集初始化
	for(int i=1;i<=n;i++) id[i]=i,sz[i]=1;//目前只有n个人
	cnt=n;//有用的 id 的个数
	for(int i=1,xx,yy;i<=m;i++)
	{
		cin>>opt;
		if(opt=='?')
		{
			scanf("%d",&x);
			x=id[x];
			xx=getf(x);
			if(sz[xx]==1) printf("%d",zt[xx]);// n=1 的情况
			else printf("%c",(zt[xx]?'1':'?'));
		}
		if(opt=='+')
		{
			scanf("%d%d",&x,&y);
			x=id[x]; y=id[y];
			xx=getf(x); yy=getf(y);
			if(xx==yy) zt[xx]=1; //联通块内成环
			else
			{
				sz[xx]+=sz[yy]; f[yy]=xx; zt[xx]|=zt[yy];// 合并连通块
			}
		}
		if(opt=='-')
		{
			scanf("%d",&x);
			xx=getf(id[x]); sz[xx]--; //删除
			id[x]=++cnt; sz[cnt]++; //增加新点
		}
	}
	return 0;
}