解题关键
到根节点距离 食物链是循环的!
在路径压缩的时候维护 find()函数
// 1 它吃根节点 x->y 吃n-1 代
// 2 根节点吃它
//3/0 它和根节点是同类
#include <iostream>
using namespace std;
const int N = 50010;
int n, m;
int p[N], d[N];
int find(int x){
if(x!=p[x]){
int t=find(p[x]); //路径压缩 直接指向根节点
d[x]+=d[p[x]]; //自己到父的距离+父亲到跟父亲的父亲(相当于不断向上递归)
p[x]=t;
}
return p[x];
}
int main(){
scanf("%d%d", &n, &m);
// 初始化 自己是一个集合
for (int i = 1; i <= n; i ++ ) p[i] = i;
int res = 0;
while (m -- )//询问
{
int t, x, y;// t 表示种类
scanf("%d%d%d", &t, &x, &y);
if (x > n || y > n) res ++ ;//超出范围
else
{
int px = find(x), py = find(y);
if (t == 1)// 判断同类
{
if (px == py && (d[x] - d[y]) % 3) res ++ ;//px == py 表示指向根节点
else if (px != py)// 父元素不同
{
p[px] = py;// px的父亲是py
d[px] = d[y] - d[x];// 合并晚应该是同类
}
}
else
{
if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;// 判断真假话 x吃y 第一代吃第0代
else if (px != py)// 不在一个集合
{
p[px] = py;//px的父亲是y 那么就存在一条边从px指向py
d[px] = d[y] + 1 - d[x];// d[x]+m-d[y]=1 ----m=d[y] + 1 - d[x];
}
}
}
}
printf("%d\n", res);
return 0;
}