题意：有一些人玩石头剪刀布，其中有一个人(称其为裁判)可以出“石头”，“剪刀”，“布”中的任意一个，其他人永远只能出相同的一个。即有的人只能出剪刀，有的人只能出石头，有的人只能出布。进行了多次对决，每次只告诉你谁赢了(或者平手)，不说谁出了什么。问能否判断出谁是裁判，裁判有多少个？若只有一个裁判，问在进行了多少次对决以后就能判断出裁判是谁。
解法：首先，判断出裁判的方法是，若1,2,3号选手的结果出现了矛盾，则1,2,3号中必有一个人是裁判，
(1)这个时候如果3,4号的对决结果出现矛盾，则判定3为裁判，然后还需要验证(即如果3为裁判，其他对决结果是不是不会有矛盾)；
(2)这个时候如果4,5号出现矛盾，则说明裁判不止一个人，与题设不符；
(3)如果之后都再也没有出现矛盾，则说明不能判断出裁判是谁。
所以，方法就是，枚举谁是裁判，判断是否所有不涉及到裁判的对决结果之间没有矛盾。如果只有一个裁判，还需要求进行了多少次对决以后就已经能判断出裁判是谁了。由以上结论不难看出，在整个枚举过程中，最大的出现矛盾的对决的编号数即为所求。
tag:并查集，good
/*
* Author: Plumrain
* Created Time: 2013-11-28 19:23
* File Name: DS-POJ-2912.cpp
*/
#include <iostream>
#include <cstdio>
#include <vector> using namespace std; #define PB push_back struct node{
int f, r;
}; int n, m, line;
node p[];
char xn[];
vector<int> ans;
int an[], bn[]; int find (int x)
{
if (x != p[x].f){
int y = p[x].f;
p[x].f = find(y);
p[x].r = (p[x].r + p[y].r) % ;
}
return p[x].f;
} void merge(int a, int b, char xx, int t1, int t2)
{
int x;
if (xx == '=') x = ;
else if (xx == '>') x = ;
else x = ; p[t1].f = t2;
p[t1].r = ( - p[a].r + x + p[b].r) % ;
} bool ok(int a, int b, char xx)
{
int x;
if (xx == '=') x = ;
else if (xx == '>') x = ;
else x = ; return x == ((p[a].r + - p[b].r) % );
} bool gao(int x)
{
for (int i = ; i < n; ++ i){
p[i].f = i;
p[i].r = ;
} for (int i = ; i < m; ++ i){
if (an[i] == x || bn[i] == x) continue; int t1 = find(an[i]), t2 = find(bn[i]);
if (t1 != t2)
merge(an[i], bn[i], xn[i], t1, t2);
if (t1 == t2)
if (!ok(an[i], bn[i], xn[i])){
line = max(line, i + );
return ;
}
}
return ;
} int main()
{
while (scanf ("%d%d", &n, &m) != EOF){
if (!m){
if (n == ) printf ("Player 0 can be determined to be the judge after 0 lines\n");
else printf ("Can not determine\n");
continue;
} for (int i = ; i < m; ++ i)
scanf ("%d%c%d", &an[i], &xn[i], &bn[i]); ans.clear();
line = ;
for (int i = ; i < n; ++ i)
if (gao(i)) ans.PB (i); int sz = ans.size();
if (sz > ) printf ("Can not determine\n");
else if (!sz) printf ("Impossible\n");
else printf ("Player %d can be determined to be the judge after %d lines\n", ans[], line);
}
return ;
}