AcWing 240. 食物链
原题链接
中等
作者:
沙鸥_3
,
2023-03-12 14:23:25
,
所有人可见
,
阅读 137
食物链
自己的理解
将三个域,同类域(x),捕食域(x+n),天敌域(x+n+n)放在一个数组里。
当y + n 的父亲是 x时 说明y是x的天敌,y吃x
当y + n +n的父亲是x时,说明x是y的天敌,x吃y
#include<iostream>
using namespace std;
const int N = 1e6+10;
int p[N],n,m,ans=0;
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >>m;
for(int i =1;i<=3*n;i++) p[i] = i;
while(m--)
{
int k,x,y;
cin >> k >> x >> y;
if(x > n|| y > n) ans++;
else if(k == 1)
{
if(find(x) == find(y + n) || find(x) == find(y + n +n)) ans++;
else
{
p[find(x)] = find(y);
p[find(x + n)] = find(y + n);
p[find(x + n + n)] = find(y + n + n);
}
}
else
{
/*x是y的天敌,x吃y,如果x和y的父节点相同即是同类,或者x的父节点是y的捕食域的父节点
即y吃x,那么这句话就是假的*/
if(find(x) == find(y) || find(x) == find(y + n)) ans++;
else
{
p[find(x)] = find(y +n +n);//x的同类都是y的天敌,将x放在y的天敌域中
p[find(x + n)] = find(y);//x捕食的都是y的同类,把x的捕食放在y的同类中
p[find(x + n + n)] = find(y + n);//x的天敌是y的捕食,把x的天敌放在y的捕食中
}
}
}
cout << ans <<endl;
return 0;
}