狼人游戏（二）
内存限制: 256 Mb时间限制: 1000 ms
题目描述
有 n 名玩家在玩狼人游戏，有一些玩家的身份是狼人。其余玩家的身份是预言家。游戏的进程中，陆续出现了 m 句发言，每句发言来自于某个玩家，发言的信息是声称另一个玩家的身份是狼人或者是预言家。
小爱猜想，狼人的发言应该永远与事实相反，而预言家的发言应该永远与事实相同。她想检查一下，她的猜想是否会与发言记录产生矛盾，如果出现矛盾，请求出她的猜想与哪一条发言最先出现矛盾。
输入格式
第一行：两个整数 n 与 m
第二行到 m+1 行：第 i+1 行有两个整数：si 和 oi，接下来有一个字符：
– 如果是 T，表示 si 宣称 oi 是预言家；
– 如果是 F，表示 si 宣称 oi 是狼人；
输出格式
如果没有矛盾，输出 Passed，否则输出第一次出现矛盾的位置。
数据范围
- 对于 30% 的数据，1≤n,m≤20；
- 对于 60% 的数据，1≤n,m≤300；
- 对于 100% 的数据，1≤n,m≤500,000；
样例数据
输入:
4 3
1 2 T
3 4 F
2 1 F
输出:
3
说明:
第三句话与第一句产生了矛盾
输入:
4 4
1 2 F
2 3 T
3 4 T
2 1 F
输出:
Passed
说明:
1是狼人，其余都是预言家，就不会有矛盾
解析：
根据发言，如果s说o是预言家，那么有两种可能：
1.s是预言家，则说的是真话，o是预言家；
2.s是狼人，则说的是假话，o是狼人；
即s和o是一伙人。
同理，若s说o是狼人，那么s和o不是一伙人。
利用并查集，将一伙人放到同一集合，对手放到另一集合，若出现矛盾，即输出。
详见代码：
#include <bits/stdc++.h>
using namespace std;
int father[1000005];//定义father[i]为己方集合，father[n+i]为对手方集合
int n, m;
int ff(int x) {//找爸爸
if (father[x] == x) return x;
father[x] = ff(father[x]);
return father[x];
}
void un(int x, int y) {//集合合并
int xx = ff(x);
int yy = ff(y);
if (xx != yy) {
father[yy] = xx;
}
return;
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) {//初始化
father[i] = i;
father[n + i] = n + i;
}
for(int i = 1; i <= m; i++) {
int x, y;
char ch;
cin >> x >> y >> ch;
if (ch == 'T') {//若说对方是预言家
//任意一方和另一方的对手是同一集合即矛盾
if (ff(x + n) == ff(y) || ff(x) == ff(y + n)) {
cout << i;
return 0;
} else {//不矛盾
un(x, y);//加入同一集合
un(x + n, y + n);//对手方加入同一集合
}
} else {//说对方是狼人
//若二人为同一集合或二人的对手方为同一集合即矛盾
if (ff(x) == ff(y) || ff(x + n) == ff(y + n)) {
cout << i;
return 0;
} else {//不矛盾
un(y, x + n);//跟另一方的对手同一集合
un(x, y + n);
}
}
}
cout << "Passed";
return 0;
}