自动搬运

查看原文

来自洛谷，原作者为

	哈哈人生 Go Best.

搬运于2025-08-24 22:52:34，当前版本为作者最后更新于2023-11-25 11:08:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

题外话

由于很多人对本题并查集做法提问，本人于二零二四年一月二十日对此篇题解进行了更新。

巧妙方法

相信大家已经知道此题的并查集、高斯消元等解法了，本人在此篇题解对此不再赘述，只是给大家提供一种代码细节——处理三值逻辑的符号的一些巧妙的方法。

我们其实可以把三值逻辑分别赋予三个值，再把这三个值赋予三个常量，常量名就以 $T$、$F$、$U$ 所命名，方便我们下面并查集中的代码编写。我们接着规定逻辑非运算就是把值的正负取反，那么 $U$ 常量的值就应该为 $0$（因为 $0=-0$）。而 $T$ 常量和 $F$ 常量的值呢？因为要把常量值和变量值区别开，我们这里取一个 $n$ 的上限加一的值，即 $100001$ 和 $-100001$。这样我们在代码编写中就可以以常量名代替繁琐的字符判断，本人认为是十分巧妙且便捷的。

本人做法

这里具体说一下并查集做法（也是更新部分）。

我们的大体思路是先按照题意模拟，给所有输入的操作的相关变量用并查集标记，在并查集查询操作前我们就可以确定哪些变量的值是确定的，哪些是不确定的，这时我们的任务就是最小化不确定的变量中 $U$ 的个数。那哪些情况的变量它的值一定是 $U$ 呢？总的来说有两种：

1. $x$ 的祖先是 $-x$。
2. $x$ 的祖先是 $U$。

我们把这两种情况查询出来，再统计个数，就是最终答案了！由于 $x$ 的值可能我们可能标记成负数了，所以并查集查询时遇到负数要取相反数，不然就会运行错误（别问我怎么知道的，哭）。

由于我们要查询的 $x$ 的祖先有可能是 $-x$，取相反数后又是 $x$，这样就会陷入死循环。于是我们需要用 $book$ 数组记录是否到过这个点的相反数（其实就是上面所写的情况一）。由于 $book$ 记录的值也有负数，所以我们要给记录的值统一加上一个 $n$ 把其全变成正数。这时需要注意 $book$ 数组的大小要开到 $2\times n$ 哦。

然后，就没有然后了（写代码呗）。

代码

上代码（马蜂良好，条件语句清楚，适宜阅读）。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int T=100001,F=-100001,U=0;//三值逻辑
int c,t,n,m,a,b,fa[100005];
char ch[100005];
bool book[300005];
int find(int x) {
	int re;
	if(x==T||x==F)re=x;
	else if(book[n-x]||x==U)re=U;
	else if(book[x+n])re=T;
	else if(x<0) {
		if(x==-fa[-x])re=x;
		else {
			book[x+n]=1;
			re=find(-fa[-x]);//这里注意细节
			book[x+n]=0;//清空
		}
	} else {
		if(x==fa[x])re=x;
		else {
			book[x+n]=1;
			re=fa[x]=find(fa[x]);
			book[x+n]=0;//清空
		}
	}
	return re;
}
signed main() {
	cin>>c>>t;
	while(t--) {
		cin>>n>>m;
		for(int i=1; i<=n; i++)fa[i]=i;
		for(int i=1; i<=m; i++) {
			cin>>ch[i];
			if(ch[i]=='T') {
				cin>>a;
				fa[a]=T;
			} else if(ch[i]=='F') {
				cin>>a;
				fa[a]=F;
			} else if(ch[i]=='U') {
				cin>>a;
				fa[a]=U;
			} else {
				cin>>a>>b;
				if(ch[i]=='+')fa[a]=fa[b];
				else fa[a]=-fa[b];
			}
		}
		int ans=0;
		for(int i=1; i<=n; i++) {
			if(find(i)==U)ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}

后记

祝点赞的人都有蓝勾！

另外，这么好的一篇题解，关注一下我呗。

站长曾经说过，不抄袭题解代码，只借鉴题解思路，但应该给题解点个赞，并且关注写题解的人（开玩笑的）。