题目来源：Codeforces Round #747 (Div. 2) D - The Number of Imposters
题意
有\(n\)个人，每个人拥有\(imposter\)或\(crewmate\)的身份，身份为\(imposter\)的人总是说假话，身份为\(crewmate\)的人总是说真话。给定\(m\)句陈述，\(i\ j\ imposter/crewmate\)，表示： \(i\) 说 \(j\) 的身份为 \(imposter/crewmate\)。
问：身份为\(imposter\)的人最多有多少个，若\(m\)个陈述存在矛盾，则输出\(-1\)。
数据范围：\(1 \le n \le 2·10^5\)，\(\sum{n} \le 2·10^5\)，\(1 \le m \le 5·10^5\)，\(\sum{m} \le 5·10^5\).
思路：带权的扩展域并查集
我们将\(imposter\)简记为\(A\)，\(crewmate\)简记为\(B\)，对于每句陈述（\(i\ j\ A/B\)）：
- 当陈述为 \(i\ j\ A\) 时，有两种可能：若 \(i\) 为 \(A\)，则 \(j\) 为 \(B\)（\(i\)说了谎）；若 \(i\) 为 \(B\)，则 \(j\) 为 \(A\)（\(i\)说真话）
- 当陈述为 \(i\ j\ B\) 时，有两种可能：若 \(i\) 为 \(A\)，则 \(j\) 为 \(A\)（\(i\)说了谎）；若 \(i\) 为 \(B\)，则 \(j\) 为 \(B\)（\(i\)说真话）
于是，我们可以用扩展域并查集，编号\([1,n]\)表示身份为\(A\)，编号\([n+1,n+n]\)表示身份为\(B\)，然后同时维护出两种可能的关系：
- 当陈述为 \(i\ j\ A\) 时：合并 \(i\) 和 \(j+n\) ，合并 \(i+n\) 和 \(j\).
- 当陈述为 \(i\ j\ B\) 时：合并 \(i\) 和 \(j\)，合并 \(i+n\) 和 \(j+n\).
在维护每个连通块的同时，维护出连通块中\(A\)身份结点的数量\(cntA\)，以及\(B\)身份结点的数量\(cntB\)。
由于每个人的身份只能是\(A\)或\(B\)，不能又是\(A\)又是\(B\)，那么出现矛盾的充要条件为：\(i\) 和 \(i+n\) 在同一连通块中，或 \(j\) 和 \(j+n\) 在同一连通块中。在每次合并后需判断一次当前是否存在矛盾，若已经存在矛盾，就不需要再进行合并了。
处理完所有陈述后，若不存在矛盾，则计算答案：遍历每个连通块，取\(cntA\)和\(cntB\)的较大值，累加到答案\(ans\)中。但由于我们同时考虑了两种可能情况，得到的答案其实是真正答案的\(2\)倍，因此最终答案应为\(\large \frac{ans}{2}\)。
时间复杂度：\(O(n + m\alpha(n))\).
代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 400010;
int n, m, p[N], cntA[N], cntB[N];
int find(int x)
{
return p[x] == x ? x : p[x] = find(p[x]);
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n + n; i++) {
p[i] = i;
cntA[i] = i <= n, cntB[i] = i > n;
}
bool flag = true; // 陈述是否互不矛盾
while(m--) {
int a, b;
string s;
cin >> a >> b >> s;
if(!flag) continue;
int pa1 = find(a), pb1 = find(b);
int pa2 = find(a + n), pb2 = find(b + n);
if(s == "imposter") {
if(pa1 != pb2) {
cntA[pa1] += cntA[pb2], cntB[pa1] += cntB[pb2];
p[pb2] = pa1;
}
// 判断合并后是否出现矛盾，已经出现矛盾就不再进行合并
if(find(a) == find(a + n) || find(b) == find(b + n)) flag = false;
if(!flag) continue;
if(pa2 != pb1) {
cntA[pa2] += cntA[pb1], cntB[pa2] += cntB[pb1];
p[pb1] = pa2;
}
} else {
if(pa1 != pb1) {
cntA[pa1] += cntA[pb1], cntB[pa1] += cntB[pb1];
p[pb1] = pa1;
}
// 判断合并后是否出现矛盾，已经出现矛盾就不再进行合并
if(find(a) == find(a + n) || find(b) == find(b + n)) flag = false;
if(!flag) continue;
if(pa2 != pb2) {
cntA[pa2] += cntA[pb2], cntB[pa2] += cntB[pb2];
p[pb2] = pa2;
}
}
// 判断合并后是否出现矛盾，已经出现矛盾就不再进行合并
if(find(a) == find(a + n) || find(b) == find(b + n)) flag = false;
}
if(!flag) {
cout << -1 << endl;
return;
}
int ans = 0;
for(int i = 1; i <= n + n; i++) {
if(p[i] == i) ans += max(cntA[i], cntB[i]);
}
cout << ans / 2 << endl;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int test;
cin >> test;
while(test--) solve();
return 0;
}