题目：poj 2912 Rochambeau（带权并查集 + 暴力）

题目大意：题目给出三个团队和一个裁判，这三个团队和裁判一起玩剪刀石头布，然后规定每个团队必须出一样的，只有裁判可以任意出。然后给出关系，x > y 代表 x 赢y ， x < y代表 y 赢 x ， 相等则出的一样。问这样的关系可以推出裁判是哪个吗？可以需要说明从第一条到第几条推出来的，不可以也要说明是不可能出现这样的关系，还是裁判不唯一。

解题思路：这题重点是裁判在里面会扰乱关系，并且n * m 才 100000，完全可以暴力。每次假设i是裁判，然后和裁判相关的关系都忽略，因为裁判可以出任意的动作。然后把剩下的组合起来，如果其中推出了矛盾的话就说明这个不是裁判，并且把第几条推出矛盾记录下来，等会会用到。然后这样判断完后如果没有一个是裁判的话，就说明这样子的关系是不存在的。如果有多个裁判说明裁判不唯一，否则就需要用到刚刚记录的矛盾出现的位置。判断第i个是裁判，就说明其他的都不是裁判，那么如果其他的都不是裁判的话，不就可以断定i是裁判，所以只要取矛盾出现的最大位置就是确定裁判的位置。

注意：这题每次判断裁判就需要执行一次并查集，要记得每次都得初始化。

代码：

#include <stdio.h>
#include <string.h>

const int N = 505;
const int M = 2005;
int n, m, f[N], c[N];
int r[M][2], vis[M];

void init () {

	for (int i = 0; i < n; i++) {

		f[i] = i;
		c[i] = 0;
	}
}

int getfather (int x) {

	if ( x != f[x] ) {

		int t = f[x];
		f[x] = getfather(f[x]);
		c[x] =  (c[x] + c[t] ) % 3;
	}
	return f[x];
}

int main () {

	char ch;
	int x, y;
	int flc, count, max, judge;
	while (scanf ("%d%d", &n, &m) != EOF) {

		//		init ();
		count = 0;
		max = 0;
		memset (vis, 0, sizeof (vis));
		for (int i = 0; i < m; i++) {

			scanf ("%d", &x);
			while (scanf ("%c", &ch) , ch == ‘ ‘);
			scanf ("%d", &y);
			if (ch == ‘<‘) {

				r[i][0] = x;
				r[i][1] = y;
			} else  if (ch == ‘>‘) {

				r[i][0] = y;
				r[i][1] = x;
			} else {

				r[i][0] = x;
				r[i][1] = y;
				vis[i] = 1;
			}
		}
		for (int i = 0; i < n; i++) {

			init ();	
			flc = 0;
			for (int j = 0; j < m; j++) {

				if (r[j][0] == i || r[j][1] == i) 	
					continue;
				int p = getfather (r[j][0]);
				int q = getfather (r[j][1]);
				int d = (vis[j] + 1) % 2;
				if (p != q) {

					f[q] = p;
					c[q] = (c[r[j][0]] - c[r[j][1]] + 3 + d) % 3;

				} else  {

					if ( (c[r[j][0]] + d) % 3 !=  c[r[j][1]]) {

						flc = j + 1;
						if (max < flc)
							max = flc;
						break;

					}
				}
			}
			if (!flc)
				count++;
			if ( !flc && count == 1) {
				judge = i;
				//				printf ("%d\n", i);
			}
		}
		if (!count)
			printf ("Impossible\n");
		else if (count > 1)
			printf ("Can not determine\n");
		else
			printf ("Player %d can be determined to be the judge after %d lines\n", judge, max);
	}
	return 0;
}