题目大意
好难概括,略
解题思路
扩展域并查集。把每个动物拆成三个节点,同类域、捕食域、天敌域。
具体代码
#include <bits/stdc++.h>
using namespace std;
const int N = 50010;
int p[N * 3], n, k, res;
int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
int main()
{
for (int i = 0; i < N * 3; i++)
p[i] = i;
cin >> n >> k;
while (k--)
{
int d, x, y;
cin >> d >> x >> y;
if (x > n || y > n) //非法编号,假话
{
res++;
continue;
}
if (d == 1) // x和y是同类
{
if (find(x + N) == find(y) || find(x) == find(y + N)) //之前说了x吃y或者y吃x,假话
{
res++;
continue;
}
p[find(x)] = find(y);
p[find(x + N)] = find(y + N);
p[find(x + 2 * N)] = find(y + 2 * N);
}
else // x吃y
{
if (x == y) // x吃x,假话
{
res++;
continue;
}
if (find(x) == find(y) || find(x) == find(y + N)) //之前说了x和y是同类或者y吃x,假话
{
res++;
continue;
}
p[find(x + N)] = find(y);
p[find(x)] = find(y + 2 * N);
p[find(x + 2 * N)] = find(y + N);
}
}
cout << res << '\n';
return 0;
}