带权并查集（poj-1182 食物链）

动物王国中有三类动物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（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

Input

第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。

Output

只有一个整数，表示假话的数目。

Sample

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

3

带权并查集的解法

定义两个数组fa[ ]和rela[ ]，fa用来判断集合关系，rela用来描述其与根节点的关系。因为关系满足传递性，所以可以推导出给出条件下的当前关系，在判断与之前已有关系是否矛盾。

本题的解法巧妙地利用了模运算，rela数组用0表示同类，1表示当前点能吃别人，2表示当前点被别人吃。

#include<cstdio>
using namespace std;
const int maxn = 50004;
int root[maxn], rela[maxn];
//先定义了两个数组，root数组来表示每个节点之间的 是否属于的关系  若a节点指向b 则说明a的祖先是b 
// rela数组来表示每个节点之间的 3种 同类（0）、捕食（1）、天敌（2） 关系 
int r, x, y, n, k;
int Find(int x) 
{
 if (x == root[x])return x;
 int tmp = root[x];
 root[x] = Find(root[x]);//压缩路径 x与根节点关系=x到父节点的关系+父节点(tmp)到根节点的关系
 rela[x] = (rela[x]+rela[tmp]+ 3) % 3; // 巧妙地利用了模运算
//rela数组用0表示这个动物和祖先是同类，1表示这个动物能吃祖先，2表示这个动物能被祖先吃 
 return root[x];//Find函数返回的是他的最终祖先 
}
//check函数 判断他们说话真假 
// 首先用根节点root数组来表示每个动物都属于他自己的集合，root[i]=i,若有两个动物A和B的祖先都不一样，则未提前声明过 则他们说的话是真的 
//当输入 r为1时，r--，进入函数时r=0 当rela[x] ==rela[y] 表示x与y是同类 有以下情况
// rela[x]=rela[y]=0，一开始初始化他们都是0 
//rela[x]=rela[y]=1，前面已经声明过他们都 能吃他们的祖先，表示他们是同类的
// rela[x]=rela[y]=2，前面已经声明过他们都 能被他们的祖先吃，表示他们是同类的
 
//当输入 r为2时，r--，进入函数时r=1 当rela[x] -rela[y]==1 表示x能吃y 有以下情况
//rela[x]=2, rela[y]=1  x被祖先吃，y吃祖先，则x吃y 
//rela[x]=1, rela[y]=0  x吃祖先，y与祖先是同一类，则x吃y 
//rela[x]=0, rela[y]=2 0-2+3==1 x初始化是0，y能被祖先吃，x和y有公共的祖先，则x吃y
 
bool check(int r, int x, int y)//bool函数 判断说假话会返回false等价返回0,判断说真话会返回true等价返回1 
//核心出口是在判断 r == (rela[x] - rela[y] + 3)%3 能判断 x吃y 还是 x和y是同一类 
//后面的 else return true 是一开始初始化 每个 Find(y)和 Find(x) 都不一样，所以返回true 
{
 if (x > n || y > n || (r == 1 && x == y))//当是谁吃谁时，x和y任一个大于n，表示说的是假话 
  return false;
 if (Find(x) == Find(y))//如果他们有公共祖先，则可以 
  //判断x与y关系(r)等于x到根关系+根到y关系(~rela[y])
  return r == (rela[x] - rela[y] + 3) % 3;// 看图，根据数学向量的思想，一个转化关系
 else return true;
}
void Union(int r, int x, int y)
{
 int fx = Find(x), fy = Find(y);//找到他们的最先的祖先 
 if (fx != fy)//如果他们的祖先不相同，则x的祖先指向y的祖先  
  {
  root[fx] = fy;//x根并入y根集合
  //更新x根到新根节点关系
  //x根到新根节点关系=根到x的关系(~relx[x])+x与y关系(r)+y到根关系
  rela[fx] = (-rela[x] + r + rela[y] + 3) % 3;
 }
}
int main() 
{
 scanf("%d%d", &n, &k);//提前声明有 n个动物，说k次话 
 for (int i = 0; i <= n; i++)
 {//初始化
  root[i] = i;//并查集模板先全部指向他们的自己， 自己的祖先是自己，用root数组记录两个动物是否在同一个集合中 
  rela[i] = 0;//用rela数组记录当前动物和祖先的关系，0表示自己和祖先是同类，1表示自己能吃祖先，不同类，2表示自己能被祖先吃，也不同类 
 }
 int ans = 0;//ans记录假话的数量 
 while (k--)
  {
  scanf("%d%d%d", &r, &x, &y); 
  r--;//注意，传参入check里都是r--后的值 
  if (check(r, x, y))//如果说的是真话，就将他们两个合并，x动物放在y动物的集合里，他们有公共祖先、 
   Union(r, x, y);
  else ans++; 
 }
 printf("%d\n", ans);
 return 0;
}

x与祖先的关系等于x与父亲的关系+父亲与祖先的关系

如果x的祖先和y的祖先相同，并不代表x，y是同一类动物，如果祖先吃x，吃y，那么祖先和x，y是两种不同的动物，x和y是相同的动物，但他们有相同的祖先（根结点）

第一次不能直接判断x和y的关系，必须先把他们转化为相同的祖先（不一定是同一种动物），只有相同祖先，才能判断他们与祖先间的关系

这里合并时候的维护，本质上就是把他们的祖先转化为相同的

在前面都控制有相同祖先的前提下才能进一步判断x，y动物的关系，利用x与祖先和y与祖先的关系，去判断x与y的关系

//当输入 r为1时，r--，进入函数时r=0 当rela[x] ==rela[y] 表示x与y是同类 有以下情况
// rela[x]=rela[y]=0，一开始初始化他们都是0 
//rela[x]=rela[y]=1，前面已经声明过他们都 能吃他们的祖先，表示他们是同类的
// rela[x]=rela[y]=2，前面已经声明过他们都 能被他们的祖先吃，表示他们是同类的

//当输入 r为2时，r--，进入函数时r=1 当rela[x] -rela[y]==1 表示x能吃y 有以下情况
//rela[x]=2, rela[y]=1  x被祖先吃，y吃祖先，则x吃y 
//rela[x]=1, rela[y]=0  x吃祖先，y与祖先是同一类，则x吃y 
//rela[x]=0, rela[y]=2 0-2+3==1 x初始化是0，y能被祖先吃，x和y有公共的祖先，则x吃y

 再注意一点：在本题中需要注意的是传入的relation恰为描述的种类号减一。也就是说要提前将输入的描述号做-1处理后传入函数中

本文章在阅读这篇博客基础上进行翻译，如有不妥，请联系作者，本着学习分享见解目的，请多多包涵，谢谢。

带权/种类并查集-POJ 1182食物链_吾仄lo咚锵的博客-CSDN博客