AcWing 258. 石头剪子布（扩展域并查集）

本文主要是介绍AcWing 258. 石头剪子布（扩展域并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

N个小朋友（编号为0,1,2,…,N-1）一起玩石头剪子布游戏。

其中一人为裁判，其余的人被分为三个组（有可能有一些组是空的），第一个组的小朋友只能出石头，第二个组的小朋友只能出剪子，第三个组的小朋友只能出布，而裁判可以使用任意手势。

你不知道谁是裁判，也不知道小朋友们是怎么分组的。

然后，孩子们开始玩游戏，游戏一共进行M轮，每轮从N个小朋友中选出两个小朋友进行猜拳。

你将被告知两个小朋友猜拳的胜负结果，但是你不会被告知两个小朋友具体使用了哪种手势。

比赛结束后，你能根据这些结果推断出裁判是谁吗？

如果可以的话，你最早在第几轮可以找到裁判。

输入格式
输入可能包含多组测试用例

每组测试用例第一行包含两个整数N和M。

接下来M行，每行包含两个整数a,b，中间夹着一个符号(‘>’,’=’,’<’)，表示一轮猜拳的结果。

两个整数为小朋友的编号,”a>b”表示a赢了b，”a=b”表示a和b平手，”a<b”表示a输给了b。

输出格式
每组测试用例输出一行结果，如果找到裁判，且只能有一个人是裁判，则输出裁判编号和确定轮数。

如果找到裁判，但裁判的人选多于1个，则输出“Can not determine”。

如果根据输入推断的结果是必须没有裁判或者必须有多个裁判，则输出“Impossible”。

具体格式可参考样例。

数据范围
1≤N≤500,
0≤M≤2000
输入样例：
3 3
0<1
1<2
2<0
3 5
0<1
0>1
1<2
1>2
0<2
4 4
0<1
0>1
2<3
2>3
1 0
输出样例：
Can not determine
Player 1 can be determined to be the judge after 4 lines
Impossible
Player 0 can be determined to be the judge after 0 lines

思路：
每个点拆成三份
$x$ :同类域
$x + n$ :能打败的域
$x + 2 * n$ :被打败的域

按照这个思路来处理点之间的关系。
我们枚举裁判点，然后出现裁判的不等式就去掉，如果中间没有矛盾就说明这是一个合法裁判。统计合法裁判的数量和出现的位置。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 2005;
struct Expr{int x,y;char op;
}expr[maxn];
int n,m;
int fa[maxn],ind[maxn];
int findset(int x) {if(fa[x] == x) return x;return fa[x] = findset(fa[x]);
}
void Union(int x,int y) {int rx = findset(x),ry = findset(y);if(rx != ry) {fa[rx] = ry;}
}
//x:同类，x+n:能打败，x+2*n:被打败
bool conflict(Expr&now) { //是否发生冲突int x = now.x,y = now.y;if(now.op == '=') {if(findset(x) == findset(y + n) || findset(x + n) == findset(y)) return true;Union(x,y);Union(x + n,y + n);Union(x + 2 * n,y + 2 * n);} else if(now.op == '>') {if(findset(x) == findset(y) || findset(x) == findset(y + n)) return true;Union(x,y + 2 * n);Union(x + n,y);Union(x + 2 * n,y + n);} else if(now.op == '<') {if(findset(x) == findset(y) || findset(x) == findset(y + 2 * n)) return true;Union(x,y + n);Union(x + n,y + 2 * n);Union(x + 2 * n,y);}return false;
}int main() {while(~scanf("%d%d",&n,&m)) {for(int i = 0;i < m;i++) {scanf("%d%c%d",&expr[i].x,&expr[i].op,&expr[i].y);}for(int i = 0;i < n;i++) ind[i] = 0;int cnt = 0;//裁判个数int id = 0;//裁判位置for(int i = 0;i < n;i++) { //枚举裁判for(int j = 0;j < n * 3;j++) fa[j] = j;int flag = 1;for(int j = 0;j < m;j++) {if(expr[j].x == i || expr[j].y == i) continue;if(conflict(expr[j])) {ind[i] = j + 1;flag = 0;break;}}if(flag) {cnt++;id = i;}}
//        printf("DEBUG %d\n",cnt);if(cnt == 0) {printf("Impossible\n");} else if(cnt == 1) {int pos = 0;for(int i = 0;i < n;i++) pos = max(pos,ind[i]);printf("Player %d can be determined to be the judge after %d lines\n",id,pos);} else {printf("Can not determine\n");}}return 0;
}