题解-Codeforces Round 805 (Div. 3) E. Split Into Two Sets

(原题链接)[Problem - E - Codeforces]

思路

知识点：种类并查集

网上关于种类并查集的教学已经很多，在此不赘述

在理解种类并查集时，很多文章会提到“敌人”，“朋友”的概念。而在不同的题目中，互为“敌人”，“朋友”的两个元素具体怎样处理是根据题目情况而确定。这里有个小技巧，就是考虑相同元素在题目中要如何操作，因为“自己和自己一定是朋友的关系”。而在本题中，比如有两个数字1，根据题目要求，同一个集合中不能有相同的数字，所以两个1一定会放在不同的集合中，也就是说，在本题中，互为朋友的两个元素一定放在不同集合中，互为敌人的元素一定放在相同集合中。

故据题意，每给出一个骨牌信息为a，b，由于这一个骨牌上的两个数字一定会放到同一个集合中，所以a，b我们应该看成敌人的关系。将a，b处理为敌人的关系用以下代码：

dsu.merge(a, b + n);
dsu.merge(b, a + n);

那什么情况下就一定不能按照题意分成两个集合了呢？因为a，b我们要处理成敌人的关系，但如果我们发现a，b已经是朋友关系了，明显出现了矛盾，这在本题中的含义就是：a和b在之前的处理中，它们应该属于不同集合，但是现在要把它们放入同一个集合，所以有了矛盾，这时就不能满足题意。

对不符题意的检验有以下两种方法：

1. 在将a，b关联为敌人关系前检验a，b是否已经是朋友关系

   if (dsu.find(a) == dsu.find(b)) {
       flag = false;//不符题意
   } else {
       dsu.merge(a, b + n);
       dsu.merge(b, a + n);
   }
   

2. 在程序结尾检验每个结点\(i\in [1,n]\)，\(i+n\)是否与\(i\)联通，因为i+n初始时就定义为i的敌人，它们是不能被联通的。如果联通了，就是不符题意。

   for (int i = 1; i <= n; ++i) {
       if (deg[i] > 2) {
           flag = false;
           break;
       }
       if (dsu.find(i) == dsu.find(i + n)) {
           flag = false;
           break;
       }
   }
   

另外一点需要知道的是，每个数字出现的次数一定为2。这很好理解因为2n个数，每个数都在\(1\dots n\)的范围内，分成两个没有重复数字的集合的话，只能是两个集合都是\({1,2,\dots ,n}\)。

AC代码

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

class DSU {
public:
	vector<int> f;
	int n;

	DSU(int _n) : n(_n) {
		f.resize(n);
		iota(f.begin(), f.end(), 0);
	}

	int find(int x) {
		int r = x;
		while (r != f[r]) {
			r = f[r] = f[f[r]];
		}
		return r;
	}

	bool merge(int x, int y) {
		int fx = find(x), fy = find(y);
		if (fx == fy) return false;
		f[fx] = fy;
		return true;
	}
};

void solve() {
	int n;
	cin >> n;
	DSU dsu(2 * n);
	vector<int> deg(n);
	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		deg[a]++;
		deg[b]++;
		dsu.merge(a, b + n);
		dsu.merge(b, a + n);
	}
	bool flag = true;
	for (int i = 0; i < n; ++i) {
		if (deg[i] > 2) {
			flag = false;
			break;
		}
		if (dsu.find(i) == dsu.find(i + n)) {
			flag = false;
			break;
		}
	}
	if (flag) cout << "YES\n";
	else cout << "NO\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t;
	cin >> t;

	while (t--) {
		solve();
	}

	return 0;
}

总结

这道题其实还有其它方法解决。如果使用种类并查集的话，有一个容易混淆的点，就是要分清并查集的联通以及题目中同一个集合的数字。因为在种类并查集中，两个结点联通说明它们是“朋友”关系，但在本题中，最终分到同一个集合中的结点两两之间是敌人的关系，也就是它们在并查集中应该是不连通的。