本文共 5294 字，大约阅读时间需要 17 分钟。

题目描述

给 $n$ 组操作，每组操作形式为$xyp$。

当 $p$ 为 $1$ 时，如果第 $x$ 个变量和第 $y$ 个变量可以相等，则输出YES，并限制他们相等；否则输出 NO，并忽略此次操作。

当 $p$ 为 $0$ 时，如果第 $x$ 个变量和第 $y$ 个变量可以不相等，则输出 YES，并限制他们不相等；否则输出 NO，并忽略此次操作。

输入格式

第一行为一个正整数 $n$。 接下来 $n$ 行每行三个整数：$x$， $y$，$p$。

输出格式

对于 $n$ 行操作，分别输出 $n$ 行 YES 或者 NO。

样例

输入

31 2 11 3 12 3 0

样例输出

YESYESNO

数据范围与提示

$1\le n\le 10^5$，$1\le x，y\le 10^8$，$p=1$ 或 $0$。

分析

显然，这是一道并查集的题。因为 $1\le x，y\le 10^8$，所以这道题需要离散化。
考虑 $p=1$ 的情况，显然把这两个集合合并就行了。
难点在 $p=0$的情况，因为$x\ne y$，$y\ne z$并不能推出$x=z$，所以这个地方没有传递性。那怎么办呢？你可以用$vis[i][j]$表示$i$和$j$不相等（只是数组不能开题目规定的这么大），还可以用$set$，将与$i$不相等的点都装进$set[i]$中（为什么不用$vector$呢？因为$set$可以自动去重）。然而我们要考虑传递：
1.数组法（比较好写）。
当 $p=0$，易知

 vis[i][j] = 1;//i ！= j vis[j][i] = 1;//同上

当 $p=1$，易知

for(int k = 1; k <= num; k ++) {        vis[i][k] |= vis[j][k];//若j != k则i != k     vis[k][i] |= vis[k][j];//同上     vis[j][k] = vis[i][k];//因为i = j，所以若i != k则j != k     vis[k][j] = vis[k][i];//同上}

2.$set$
当 $p=0$

s[i].insert(j); //插入s[j].insert(i); //同上

当 $p=1$

if(rank[i] < rank[j]) {   	fa[i] = j;	for(set <int>::iterator it = s[i].begin(); it != s[i].end(); it ++) {   		s[j].insert(*it);//因为i = j，所以若(*it) != i，则(*it) != j	}	for(set <int>::iterator it = s[j].begin(); it != s[j].end(); it ++) {   		s[*it].insert(j);//若(*it) != j，则将j加入到set[(*it)]中	}}else {   	fa[j] = i;	if(rank[i] == rank[j]) rank[i] ++;	for(set <int>::iterator it = s[j].begin(); it != s[j].end(); it ++) {   		s[i].insert(*it);//因为i = j，所以若(*it) != j，则(*it) != i	}	for(set <int>::iterator it = s[i].begin(); it != s[i].end(); it ++) {   		s[*it].insert(i);//若(*it) != i，则将i加入到set[(*it)]中	}}

这里我用了启发式合并，因为$i=j$，对于任意的$k$，如果 $i!=k$（即 $k$ 在 $set[i]$ 中），则 $j!=k$（即 $k$ 在 $set[j]$ 中）。同理，$i$ 和 $j$ 都在 $set[k]$ 中。

代码

法一

#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>#include <climits>using namespace std;const int MAXN = 2 * 1e5 + 5;int n, fa[MAXN], rank[MAXN], lsh[MAXN], X[MAXN], Y[MAXN], Z[MAXN], cnt, num;bool vis[25000][25000];void Make_Set(int x) {   	for(int i = 1; i <= x; i ++) {   //初始化		fa[i] = i;		rank[i] = 1;	}	return;}int Find_Set(int x) {   //找父亲（路径压缩）	if(x != fa[x]) {   		return fa[x] = Find_Set(fa[x]);	}	return fa[x];}bool Union_Set(int x, int y, int z) {   //合并	int i = Find_Set(x), j = Find_Set(y);	if(z == 1) {   		if(i == j) return 1;		if(vis[i][j]) return 0;		if(rank[i] < rank[j]) fa[i] = j;		else {   			fa[j] = i;			if(rank[i] == rank[j]) rank[i] ++;		}		for(int k = 1; k <= num; k ++) {   			vis[i][k] |= vis[j][k];			vis[k][i] |= vis[k][j];			vis[j][k] = vis[i][k];			vis[k][j] = vis[k][i];		}	}	else {   		if(i == j) return 0;		vis[i][j] = 1;		vis[j][i] = 1;	}	return 1;}int main() {   	int x, y;	scanf("%d", &n);	for(int i = 1; i <= n; i ++) {   		scanf("%d%d%d", &X[i], &Y[i], &Z[i]);		lsh[++ cnt] = X[i]; lsh[++ cnt] = Y[i]; 	}	sort(lsh + 1, lsh + 1 + cnt);//离散化	num = unique(lsh + 1, lsh + 1 + cnt) - lsh - 1;	Make_Set(num);	for(int i = 1; i <= n; i ++) {   		x = lower_bound(lsh + 1, lsh + 1 + num, X[i]) - lsh;		y = lower_bound(lsh + 1, lsh + 1 + num, Y[i]) - lsh;		if(Union_Set(x, y, Z[i])) printf("YES\n");		else {   			printf("NO\n");		}	}	return 0;}

法二

#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>#include <climits>#include <vector>#include <set>using namespace std;const int MAXN = 2 * 1e5 + 5;int n, fa[MAXN], rank[MAXN], lsh[MAXN], X[MAXN], Y[MAXN], Z[MAXN], cnt, num;set <int> s[MAXN];void Make_Set(int x) {   //初始化	for(int i = 1; i <= x; i ++) {   		fa[i] = i;		rank[i] = 1;	}	return;}int Find_Set(int x) {   //找父亲（路径压缩）	if(x != fa[x]) {   		return fa[x] = Find_Set(fa[x]);	}	return fa[x];}bool Union_Set(int x, int y, int z) {   //合并	int i = Find_Set(x), j = Find_Set(y);	if(z == 1) {   		if(i == j) return 1;		set <int>::iterator it = s[i].find(j);		set <int>::iterator it1 = s[j].find(i);		if(it != s[i].end() || it1 != s[j].end()) return 0;		if(rank[i] < rank[j]) {   			fa[i] = j;			for(set <int>::iterator it = s[i].begin(); it != s[i].end(); it ++) {   				s[j].insert(*it);			}			for(set <int>::iterator it = s[j].begin(); it != s[j].end(); it ++) {   				s[*it].insert(j);			}		}		else {   			fa[j] = i;			if(rank[i] == rank[j]) rank[i] ++;			for(set <int>::iterator it = s[j].begin(); it != s[j].end(); it ++) {   				s[i].insert(*it);			}			for(set <int>::iterator it = s[i].begin(); it != s[i].end(); it ++) {   				s[*it].insert(i);			}		}	}	else {   		if(i == j) return 0;		s[i].insert(j); 		s[j].insert(i);	}	return 1;}int main() {   	int x, y;	scanf("%d", &n);	for(int i = 1; i <= n; i ++) {   		scanf("%d%d%d", &X[i], &Y[i], &Z[i]);		lsh[++ cnt] = X[i]; lsh[++ cnt] = Y[i]; 	}	sort(lsh + 1, lsh + 1 + cnt);//离散化	num = unique(lsh + 1, lsh + 1 + cnt) - lsh - 1;	Make_Set(num);	for(int i = 1; i <= n; i ++) {   		x = lower_bound(lsh + 1, lsh + 1 + num, X[i]) - lsh;		y = lower_bound(lsh + 1, lsh + 1 + num, Y[i]) - lsh;		if(Union_Set(x, y, Z[i])) printf("YES\n");		else {   			printf("NO\n");		}	}	return 0;}