[NOI 2001] 食物链

知识点

并查集、关系建模、同余关系

解题思路

为动物x建立x、x+n、x+2n三个关系节点。用“x与y+n同集合”表示x吃y。若陈述同类，先排除x已经与y的另外两类相同，再合并三对同类节点。若陈述吃，排除同类和反向捕食，再合并(x,y+n)、(x+n,y+2n)、(x+2n,y)。编号不在1到n的陈述直接判假。

正确性说明

三倍域把每个动物的三种循环类型表示成等价类，合并同步保持模3关系。每次先检查新关系是否与已有关系相冲突，冲突则不写入；否则三次合并恰好添加该关系及其循环推论。归纳保证并查集只包含之前真话的全部等价推论，所以假话计数正确。

易错点

假话不能写入并查集；自己吃自己必冲突；同类关系对称，捕食关系有方向；输入编号范围大于32位有符号整数，先用long long读取并判断范围。

复杂度

时间O((n+k)α(n))，空间O(n)，使用按大小合并与路径压缩。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
struct DSU{vector<int>p,s;DSU(int n):p(n+1),s(n+1,1){iota(p.begin(),p.end(),0);}int find(int x){while(x!=p[x]){p[x]=p[p[x]];x=p[x];}return x;}bool same(int x,int y){return find(x)==find(y);}void join(int x,int y){x=find(x);y=find(y);if(x==y)return;if(s[x]<s[y])swap(x,y);p[y]=x;s[x]+=s[y];}};
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,k;cin>>n>>k;DSU d(3*n);int ans=0;while(k--){int op;long long xx,yy;cin>>op>>xx>>yy;if(xx<1||xx>n||yy<1||yy>n){++ans;continue;}int x=xx,y=yy;if(op==1){if(d.same(x,y+n)||d.same(x,y+2*n)){++ans;continue;}d.join(x,y);d.join(x+n,y+n);d.join(x+2*n,y+2*n);}else{if(d.same(x,y)||d.same(x,y+2*n)){++ans;continue;}d.join(x,y+n);d.join(x+n,y+2*n);d.join(x+2*n,y);}}cout<<ans<<'\n';}