大意：n 个人 ，每个人要么是好人，要么是坏人，好人只说真话，坏人只说假话。给定 一些关系，即a b c 代表 a说b的身份是 c。现要确定他们的什么，在不矛盾的前提下，问最多可以有多少坏人。输出坏人的人数，若关系存在矛盾输出-1。
思路：a 说 b 的身份是 c ，我们坏人记作c=0,好人记作c=1。当 c=0 时，即 a说b 是坏人，当 a是好人是，那么 b 就是坏人，当a 是坏人时，b实际上是好人。二人身份相异。
当 c=1 时，a说 b 是好人，当 a是好人时，那么b也是好人，当 a是坏人时，b也是坏人，二人身份相同。
通过分析我们发现，二人的身份要么相同，要么相异。并且具有传递性，即 ab 相异，bc 相异，那么 ac相同。所以我们可以用带权并查集来写，利用到根节点的距离奇偶性来区别身份异同，即到根节点的距离为偶数时与根节点身份相同，为奇数时与根节点身份不同。
当两人已经在用同一个连通块中，并且之前的身份信息和新输入的身份信息不一样时产生矛盾。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200010;
int fa[N],dt[N],cnt[N][2];
int n,m;
void init()
{
for(int i=1;i<=n;i++)
{
fa[i]=i;
dt[i]=0;
cnt[i][0]=1;
cnt[i][1]=0;
}
}
int find(int x)
{
if(fa[x]!=x)
{
int px=find(fa[x]);
dt[x]^=dt[fa[x]];
fa[x]=px;
}
return fa[x];
}
void solve()
{
cin>>n>>m;
init();
bool f=1;
for(int i=1;i<=m;i++)
{
char str[10];
int a,b,c;
cin>>a>>b>>str;
c=(str[0]=='i'); // 这样赋值可以做到下面不用分类讨论
int pa=find(a),pb=find(b);
if(pa==pb)
{
if((dt[a]^dt[b])!=c)f=0;
}
else
{
fa[pb]=pa;
dt[pb]=c^dt[a]^dt[b];//经过推导推出公式，省的分类讨论
cnt[pa][0]+=cnt[pb][dt[pb]];
cnt[pa][1]+=cnt[pb][dt[pb]^1];
}
}
if(!f)
{
cout<<-1<<"\n";
return ;
}
int res=0;
for(int i=1;i<=n;i++)
{
int pi=find(i);
if(pi==i)res+=max(cnt[pi][0],cnt[pi][1]);
}
cout<<res<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int _=1;
cin>>_;
while(_--)solve();
return 0;
}
总结：各种关系约束、限制类的匹配问题，看能不能用并查集写。