食物链

先看题目要求

算法1

(并查集维护关系)

1.由题意可知只有三种动物，三种动物之间的关系是循环的（由于是环形），可以通过对3取模来判断是哪一种关系

2.可以利用并查集维护这三种动物值间的关系，也就是说集合表示的是每一个点到根节点的距离

因此需要一个数组，记录每一个点到根节点的距离，从而可以推断出任意两点之间的关系 （一个点到根节点的距离 % 3）

3.一共有三种关系：

1)与根节点的距离为 1 (余1) ,表示该点吃根节点

2)与根节点距离为 2 (余2)， 表示他被根节点吃

3)与根节点距离为 0 (余0)，表示该点与根节点是同一类

代码实现细节

1.初始化：

一开始所有动物都是独立的一个集合，并且自己到自己的距离为 0

int dist[N];    //全局变量默认值就是0

for(int i=1;i<=n;i++){
    p[i]=i;    //并查集初始化
}

2.路径压缩的同时，需要更新距离：

从他到父节点的距离 + 父节点到根节点的距离 = 他到根节点的距离

int find(int x){
    if(p[x] != x)   //如果不是父节点
    {   
        int fu = find(p[x]);   //找根节点
        
        dist[x] += dist[p[x]];  //他到根节点的距离
        
        //dist[p[x]] 就是父节点到根节点的距离
        
        p[x] = fu;   //父节点指向根节点 - 路径压缩
    }
}

3.判断同类关系：

1.属于同一个集合时两个点到根节点的距离取模3结果一样，表示同一类

dist[x]% 3 == dist[y]% 3
dist[x]% 3 - dist[y]% 3 == 0
(dist[x] - dist[y] )%3 == 0

2.不属于一个集合时，首先合并两个集合，更新根节点到另一个根节点的距离

int px = find(x), py - find(y);

if(px!=py){
    p[px] = py;   //合并两个集合，将py 成为 px的根节点
    dist[px] = dist[y] - dist[x];   //更新px到 py的距离
}

如何求px到py的距离

合并之后到两个集合到根节点的距离时相同的

(dist[x] + ?)% 3 == dist[y]% 3
dist[x] +? == dist[y]
? = dist[y] - dist[x]

4.判断吃与被吃关系：

比如: X 吃 Y

1.属于一个集合时，x到根节点的距离比y到根节点的距离多1，因为x 到 y 的距离为 1

因此，判断x-1到根节点的距离是否等于 y到根节点的距离即可

(dist[x]-1)% 3 == dist[y]% 3
(dist[x]-1)% 3 - dist[y]% 3 == 0
(dist[x] - 1 - dist[y] )%3 == 0

2.不属于一个集合，首先合并两个集合，在更新根节点到另一个根节点的距离

((dist[x] - 1) + ?)% 3 == dist[y]% 3
(dist[x] - 1) +? == dist[y]
? = dist[y] - dist[x] + 1

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int n,m;
int p[N];  //并查集
int dist[N];  //该点到根节点的距离
int res;

int find(int x){
    if(p[x]!=x){
        int fu = find(p[x]);  //找根节点
        dist[x] += dist[p[x]]; 
        p[x] = fu;
    }
    return p[x];
}
int main(){
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=n;i++)  p[i]=i;
    
    while(m--){
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        
        if(x > n || y > n) {
            res++;
            continue;
        }
        
        int px = find(x), py = find(y);
        
        if(op==1) {  
         
            if(px==py && (dist[x]-dist[y])%3 ) res++;
            else if(px != py){
                p[px] = py;  
                dist[px] = dist[y] - dist[x]; 
            }
        }else {
            if(px==py && (dist[x] - 1 -dist[y]) % 3) res++;
            else if(px != py){
                p[px] =py;
                dist[px] = dist[y] - dist[x] + 1;
            }
        }
    }
    
    printf("%d",res);
    return 0;
}