题目描述
动物王国中有三类动物 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 句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
当前的话与前面的某些真的话冲突，就是假话；
当前的话中 X 或 Y 比 N 大，就是假话；
当前的话表示 X 吃 X，就是假话。
你的任务是根据给定的 N 和 K 句话，输出假话的总数。输入描述
第一行是两个整数 N 和 K，以一个空格分隔。
以下 K 行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。
若 D=1，则表示 X 和 Y 是同类。
若 D=2，则表示 X 吃 Y。输出描述
只有一个整数，表示假话的数目。
1≤N≤50000
0≤K≤100000示例
输入
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5输出
3
分析
如何去合适的表达动物之间的关系是本题的难点。借鉴并查集，通过其它元素来间接的得到两个元素的关系。
我们建立一个并查集，用这棵树来表示该集合间的关系，并维护元素到根节点的距离的数组。给出并查集中部分结构如下：
显然，该结构中任一动物与A的关系可由距离模三得出，而任意两个动物之间的关系则可由二者跟A的关系推出。
因此，此时所建立的并查集表示的是一组动物之间的关系，与传统并查集所表示的元素的分类完全不同，只是借用了并查集的操作与思想。
当出现两个不在同一并查集里的动物时，我们就可以合并这两个并查集，合并时要对距离数组进行修改以保持动物之间的关系不变。
诸多细节详见代码及注释。
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50005;
int n, m;
int p[N], d[N];
int find(int x)
{
if (p[x] != x)
{
int t = find(p[x]); //注意！！！
d[x] += d[p[x]]; //若根节点到根节点的距离不是0
p[x] = t; //则每调用一次find d[x]都会变化 产生错误
}
return p[x];
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
p[i] = i;
int res = 0;
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
if (b > n || c > n)
{
res++;
continue;
}
int pb = find(b);
int pc = find(c);
if (a == 1)
{
if (pb == pc && (d[b] - d[c]) % 3)
{
res++;
continue;
}
if (pb == pc) //若两节点已在同一棵树中 则无需合并
continue;
p[pb] = pc;
d[pb] = d[c] - d[b];
/* 下面这种更新方式是错误的
* d[find(b)] = d[c] - d[b];
* 这一行将使根节点到根节点的距离不为0
* p[find(b)] = find(c);
* 而这一行在该情况下调用find将使整个并查集中的d数组出错*/
}
else
{
if (b == c)
{
res++;
continue;
}
if (pb == pc && (d[b] - d[c] - 1) % 3)
{
/* 对(d[b] - d[c] - 1) % 3的解释
* d[b]和d[c]的大小关系未知，而C++中负数对
* 3取余的值可能是负数，因此将最终判定落在0上就很好*/
res++;
continue;
}
if (pb == pc)
continue;
d[pb] = d[c] - d[b] + 1;
p[pb] = pc;
}
}
cout << res << endl;
return 0;
}
