算法1

(并查集) $O(k)$

题目大意：有3类动物食物链成环，现给出n个动物的之间的若干条关系，对每个描述判断有多少是与之前的结论冲突的。

题解： 首先可以处理掉题目中给出的一些很显然的错误，包括自己吃自己，编号大于n。然后就是要处理当前的描述是否与之前的描述能得到的结论冲突。

我们将一个动物拆成3个来存储，一个代表自身，第二个代表它的猎物，第三个代表它的天敌。

例如：$x$ 和 $y$ 是同类，那么 $x$ 的猎物和 $y$ 的猎物也应该是同类，$x$ 的天敌和 $y$ 的天敌也应该是同类，那么这些同类应该在并查集中是连通的。

再例如：$x$ 吃 $y$，那么 $x$ 的猎物和 $y$ 是同类，$y$ 的猎物和 $x$ 的天敌应该是同类，这些同类都应该连通在同一个连通块中。

对于每一个输入，通过已有的连通信息判断是否错误，如果不是错误的，那么就可以作为新的信息来使用了。

C++ 代码

#include <iostream>

using namespace std;

const int N = 5e4 + 10;

int n, k, ans;
int p[N * 3]; // 注意要开3倍大小 

// 并查集模版部分
int find(int x) {
    if (p[x] == x) return x;
    return p[x] = find(p[x]);
} 

inline void Union(int x, int y) {
    p[find(x)] = find(y);
} 

inline bool SameSet(int x, int y) {
    return find(x) == find(y);
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 1; i <= 3 * n; ++i) p[i] = i;

    for (int i = 1, c, x, y; i <= k; ++i) { 
        if (cin >> c >> x >> y, x <= n && y <= n) {
            if (c == 1) { // 对给出的同类关系 
                // x和y的猎物以及y的天敌都不能是同一类的，否则就是错误的 
                if (!SameSet(x, y + n) && !SameSet(x, y + 2 * n)) {
                    // 不是错误的信息可以得到3个同类关系 
                    Union(x, y), Union(x + n, y + n), Union(x + 2 * n, y + 2 * n);
                }
                else ++ans;
            }
            else {
                if (x != y) { 
                    // x和y不是同一类，x的天敌y+n和x也不是同一类，否则就是错误的 
                    if (!SameSet(x, y) && !SameSet(x, y + n)) {
                        // 得到新的关系 
                        Union(x, y + 2 * n), Union(x + n, y), Union(x + 2 * n, y + n);
                    }
                    else ++ans;
                }
                else ++ans; // 如果自己吃自己，那么显然是错误的 
            }
        }
        else ++ans; // 如果编号大于n那么显然是错误的 
    }

    cout << ans << '\n';

    return 0;
}

算法2

(带权并查集) $O(k)$

类似地可以在边上存0代表是同类， 存1代表是猎物，
存$2$代表是天敌，可以得到，路径上的边权和模3就是两者之间的关系。例如，最简单的，猎物的猎物是天敌这一情况，两次边权为$1$的相加得到$2$，代表是天敌，再例如，天敌的猎物是同类，边权$2+1==3$，模$3$后为$0$，即代表同类。可见，使用带权并查集解这道题非常好理解而且好写。

C++ 代码

#include <iostream>

using namespace std;

const int N = 5e4 + 10;

int n, k, ans;
int p[N], val[N];

// 并查集核心操作 
int find(int x) {
    if (x == p[x]) return x;
    int new_p = find(p[x]);
    val[x] = (val[x] + val[p[x]]) % 3; //带权并查集更新关系 
    p[x] = new_p; // 路径压缩 
    return new_p;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) p[i] = i, val[i] = 0;

    for (int i =1, c, x, y; i <= k; ++i) {
        if (cin >> c >> x >> y, x <= n && y <= n) {
            if (c == 1) {
                if (find(x) == find(y)) 
                   ans += val[x] != val[y];
                else {
                    val[p[x]] = (val[y] - val[x] + 3) % 3;
                    p[p[x]] = p[y];
                    // 建立新的边，可以考虑带权并查集的那个四边形 
                }
            }
            else {
                if (x != y) {
                    if (find(x) == find(y))
                       ans += val[x] != (val[y] + 1) % 3;
                    else {
                        val[p[x]] = (val[y] + 1 - val[x] + 3) % 3;
                        p[p[x]] = p[y];
                        // 类似的处理 
                    }
                }
                else ++ans;
            }
        }
        else ++ans;
    }

    cout << ans << '\n';

    return 0;
}