1390：食物链【NOI2001】

【解题思路】

并查集把三类动物划分成三个域，同类域（1-n）、捕食域〈n+1-2n）、天敌域（2n+1-3n）。把x放入同类域，x+n放入其捕食域，x+2n放入其天敌域。给×在其他集合内安插两个“虚拟代表”，从而实现关系传递。

×吃y，则×与y的天敌代表y+2n是同类，合并区y+2n)；

×吃y，则×的捕食代表×+n与y是同类，合并(x+n,y)；

x吃y，则×的天敌代表x+2n与y的捕食代表y+n是同类，合并(x+2n,y+n)。

例如，n=10，1吃2，2吃3，3吃4。

1吃2：（1，22）（11，2）（21，12）

2吃3：（2，23）（12，3）（22，13）

3吃4：〔3，24）（13，4）（23，14）

通过代表22和13，把1与4合并到一起。

【参考代码】

//示例代码
#include <iostream>
#include <cstdio>
using namespace std;const int N=150005;   // 定义常量 N，表示数组大小
int n,k,F;           // n 表示点的数量，k 表示操作数， F 表示不合法的操作数。
int f[N];            // 数组 f 存储点的祖先// 并查集中的查找操作，实现路径压缩
int find(int x){if(f[x]==x) return f[x];return f[x]=find(f[x]);
}// 并查集中的合并操作
void unionn(int x,int y){x=find(x);y=find(y);if(x!=y) f[y]=x;
}int main()
{scanf("%d %d",&n,&k);  // 输入点的数量和操作数for(int i=1;i<=n*3;i++)f[i]=i;  // 初始化并查集，每一个点是其自己的祖先。int d,x,y;   // d 表示每个操作的类型，x、y 表示需要连接的两个点的编号。while(k--){scanf("%d %d %d",&d,&x,&y);if(x>n||y>n){  // 判断输入的点是否合法。如果一个点的编号大于 n，代表这个操作是不合法的。F++; continue;}else if(d==1){   // 如果操作类型为 1，x,y为同类if(find(x)==find(y+n) || find(x)==find(y+n*2))  F++; // 如果x的猎物是y或y的天敌  为假else{  // 否则，合并。unionn(x,y);//同类合并unionn(x+n,y+n);//x的天敌和y的天敌是同类unionn(x+2*n,y+2*n);//x的猎物也和y的猎物是同类}    }else if(d==2){   // 如果操作类型为 2，x的猎物是y。if(find(x)==find(y) || find(x)==find(y+n*2))  F++; // 如果x,y同类 或 x的天敌是y  则假。else{  // 否则，合并。unionn(x,y+n);//x的猎物是yunionn(x+n,y+2*n);//x的天敌也是y的猎物unionn(x+2*n,y);//y的天敌是x}    }}printf("%d",F);   // 输出不合法操作的数量。return 0;
}