Problem Description
现有M个人一起玩剪刀石头布，以1－M编号，每人出一种，出过不再改变，但是我们并不知道它到底是哪一种。 （其中石头赢剪刀，剪刀赢布，布赢石头，一样则平） 裁判用两种说法对这M个人所构成的输赢关系进行描述： 一："1 A B"，表示第A个人和第B个人出的一样。 二："2 A B"，表示第A个人赢第B个人。 裁判对M个人，用以上两种说法，连说N句话，其中有真的、也有假的。 一句话出现以下情况，就是假话，否则就是真话。 1） 该句话与之前的某些真话冲突； 2） 该句话中A或B比M大； 3） 该句话表示A赢A。 请根据给定的M和N，输出假话数。 其中（1 <= M <= 10,000），（0 <= N <= 10,000）
Input
第1行是一个自然数K，代表有K组数据。 每组数据以一个空行分隔，其中每组数据的第1行是两个自然数M、N，以空格分开。 每组数据的第2行至N+1行，每行是三个自然数X，A，B，三个数之间用空格分开，X（1或2）表示说法的种类。
Output
每组数据对应一行，每行有一个整数，代表假话数。
3
43 11
1 4 3
2 3 3
1 4 1
1 4 4
2 3 3
1 2 2
2 1 4
1 1 1
2 1 4
2 3 4
2 3 2
66 9
2 3 1
2 4 4
2 1 2
2 4 3
2 4 2
2 2 3
1 3 2
1 2 1
1 1 1
6 7
2 3 7
2 1 2
2 4 4
1 2 1
1 3 2
1 2 3
2 1 3
Sample Output
5 4 3
分析：经典并查集
#include#include using namespace std;const int MAX_N = 50010;int set[MAX_N];int r[MAX_N];void init(int n){ for (int i = 0; i <= n; i++) { set[i] = i; r[i] = 0; }}int cha(int x){ if (x == set[x]) return x; int tx = cha(set[x]); r[x] = (r[x] + r[set[x]]) % 3; return set[x] = tx;}void unite(int x, int y, int type){ int tx = cha(x); int ty = cha(y); set[ty] = tx; r[ty] = (r[x] + type - 1 - r[y] + 3) % 3; return;}int main(){ int n(0), m(0); int xx; scanf("%d",&xx); while(xx--) { scanf("%d%d", &n, &m); init(n); int type(0), x(0), y(0); int ans(0); for (int i = 1; i <= m; i++) { scanf("%d%d%d", &type, &x, &y); if (x > n || y > n || (type == 2 && x == y)) { ans++; continue; } if (cha(x) == cha(y)) { if ((r[y] - r[x] + 3) % 3 != (type - 1)) { ans++; } } else { (unite(x, y, type)); } } printf("%d\n", ans); }}