大连网站制作仟亿科技,北京app开发制作,网站备案信息找回,成都百度推广动物王国中有三类动物 A,B,C#xff0c;这三类动物的食物链构成了有趣的环形。
A 吃 B#xff0c;B 吃 C#xff0c;C 吃 A。
现有 N 个动物#xff0c;以 1∼N 编号。
每个动物都是 A,B,C 中的一种#xff0c;但是我们并不知道它到底是哪一种。
有人用两种说法对这 N…动物王国中有三类动物 A,B,C这三类动物的食物链构成了有趣的环形。
A 吃 BB 吃 CC 吃 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 行每行是三个正整数 DXY两数之间用一个空格隔开其中 D 表示说法的种类。
若 D1则表示 X 和 Y 是同类。
若 D2则表示 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
代码
#includeiostream
using namespace std;const int N 50010;
int father[N],d[N];int findroot(int x){if(father[x] ! x){int temp findroot(father[x]);d[x] d[father[x]];father[x] temp;}return father[x];
}int main(){int n,k;cinnk;for(int i 0;in;i){father[i] i;d[i] 0;}int fake 0;while(k--){int op;cinop;int x,y;cinxy;if(x n || y n){fake;}else{int px findroot(x);int py findroot(y);if(op 1){if((px py) ((d[x]-d[y])%3! 0)){fake;}else if(px ! py){father[px] py;d[px] d[y] - d[x];}}else if(op 2){if((px py) ((d[x]-d[y]-1)%3! 0)){fake;}else if(px ! py){father[px] py;d[px] d[y] - d[x] 1;}}}}coutfakeendl;return 0;
}
