本题目的关键在于将动物的类别转化成节点的距离从而利用并查集的特点进行求解
A吃B, B吃C,C吃A a标记为0 b为1 c为2 取模同余则为同类
题目描述
动物王国中有三类动物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和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
算法1
参考文献
大雪菜的精彩讲解
C++ 代码
//并查集来维护额外信息
#include<iostream>
using namespace std;
const int N=50010;
int p[N],d[N];//d表示距离
int n,m;
int find(int x)//返回x的祖宗节点
{
if (p[x] != x)
{
int t = find(p[x]);//t此时变成了px的祖宗节点
d[x] += d[p[x]];//dx原本是x到原本祖宗节点(即原本的px)的距离 再加上px到根节点的距离 就是x到根节点的距离了
p[x] = t;
}
return p[x];//递归实现路径压缩
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
int res = 0;
while (m -- )
{
int t, x, y;//t表示说话的种类
scanf("%d%d%d", &t, &x, &y);
if (x > n || y > n) res ++ ;//假话的条件二: 不能超过种类个数
else
{
int px = find(x), py = find(y);
if (t == 1) //x和y是同类
{
//px==py说明在同一个并查集之下了而 (d[x]-d[y])%3!=0 那么他们并不是同一类
if (px == py && (d[x] - d[y]) % 3) res ++ ;//是假话了
else if (px != py) //不在同一个集合中 不妨先让py成为了px的祖宗节点
{
p[px] = py;
d[px] = d[y] - d[x];//即(dx+?-dy)%3==0 因为x和y是同一类 dx+?的距离和dy是同余的
}
}
else//x应该是吃y的
{
if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;//那么dx应该比dy多一
else if (px != py)
{
p[px] = py;
d[px] = d[y] + 1 - d[x]; //(dx-1+?)和dy同余 那么(dx-1+?-dy)%3==0 ?=dy+1-dx;
}
}
}
}
printf("%d\n", res);
return 0;
}
d数组一开始不全是0嘛,在find函数里怎么会变呢
d[px] = d[y] + 1 - d[x]; //(dx-1+?)和dy同余 那么(dx-1+?-dy)%3==0 ?=dy+1-dx;
d[px] = d[y] - d[x];//即(dx+?-dy)%3==0 因为x和y是同一类 dx+?的距离和dy是同余的
这两行会使它改变