洛谷 P2024 [NOI2001] 食物链
题目描述
动物王国中有三类动物 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，表示有 N 个动物，K 句话。
第二行开始每行一句话。格式见题目描述与样例。
输出格式
一行，一个整数，表示假话的总数。
输入输出样例
输入 #1复制
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5输出 #1复制
3说明/提示
对于全部数据，1≤N≤5×104，1≤K≤105。
#include<bits/stdc++.h> using namespace std; const int N=5e4+10; int fa[N*3];//扩展域并查集 int n,k; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } void un(int x,int y) { fa[find(x)]=find(y); } int main() { cin>>n>>k; int ret=0; //初始化 for(int i=1;i<=3*n;i++) { fa[i]=i; } for(int i=1;i<=k;i++) { int op,x,y; cin>>op>>x>>y; if(x>n||y>n) ret++; else if(op==1)//同类 { //x->y y->x if(find(x)==find(y+n+n)||find(y+n)==find(x)) { ret++; }else{ un(x,y); un(x+n,y+n); un(x+n+n,y+n+n); } }else//x->y { //y->x 同类 if(find(x)==find(y)||find(y+n+n)==find(x)) { ret++; }else{ un(y,x+n+n); un(y+n,x); un(y+n+n,x+n); } } } cout<<ret<<endl; return 0; }