1921 - 食物链
时间限制 : 1 秒
内存限制 : 128 MB
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。
题目输入
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
题目输出
只有一个整数，表示假话的数目。
输入/输出样例
输入格式
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
输出格式
3
C++解答
//用0，1，2分别表示3种动物 #include<stdio.h> #include<string.h> #define Max 50010 //rank[i]:记层数; father[i]:记i的根结点; link[i]: 以i的根为0为基准i属于的动物种类为link[i]; int rank[Max]; //i从link[i]变为j种动物: link[i] = (link[i]+step[j][link[i]])%3 int step[3][3] = {{0, 2, 1}, {1, 0, 2}, {2, 1, 0}}; int n, k, d, x, y, wrong; struct PP { int father; int link; }p[Max]; //初始化：每个元素就是一个集合 void set(int n) { for(int i = 1; i <= n; i++) { p[i].father = i; rank[i] = 0; p[i].link = 0; } } //寻找元素所在集合的根，使用路径压缩来优化该函数 PP f(int i) { PP t; if(p[i].father != i) { t = f(p[i].father); p[i].father = t.father; p[i].link = (t.link+p[i].link)%3; } return p[i]; } // 若为真将x和y所在的集合合并 void Union(int a, int b) { if(a != b){ //要合并的 if(rank[a] >= rank[b]){ p[b].father = a; if(rank[a] == rank[b]) rank[a]++; if(d == 2) p[b].link = (p[b].link+step[(p[x].link+1)%3][p[y].link])%3; else if(d == 1) p[b].link = (p[b].link+step[p[x].link][p[y].link])%3; } else if(rank[a] < rank[b]){ p[a].father = b; if(d == 2) p[a].link = (p[a].link+step[(p[y].link+2)%3][p[x].link])%3; else if(d == 1) p[a].link = (p[a].link+step[p[y].link][p[x].link])%3; } } else{ //不需要合并的 if(d == 1 && p[x].link != p[y].link)wrong++; else if(d == 2 && (p[x].link+1)%3 != p[y].link)wrong++; } } int main() { //freopen("eat.in", "r", stdin); //freopen("eat.out", "w", stdout); int i; PP t1, t2; scanf("%d%d", &n, &k); set(n); for(wrong = i = 0; i < k; i++) { scanf("%d%d%d", &d, &x, &y); if(x > n || y > n){ wrong++; continue; } if(x == y) { if(d == 2) wrong++; continue; } t1 = f(x); t2 = f(y); Union(t1.father, t2.father); } printf("%d\n", wrong); return 0; }