并查集实用操作: 通过扩展并查集的值域来实现维护额外信息.

例: P2024 [NOI2001] 食物链

动物王国中有三类动物 \(A,B,C\), 这三类动物的食物链构成了有趣的环形. \(A\) 吃 \(B\), \(B\) 吃 \(C\), \(C\) 吃 \(A\).

若共 \(n\) 个动物, 对于一个动物 \(i\) , 我们设 \(i\) 代表和 \(i\) 一类的集合, \(i + n\) 代表 \(i\) 的食物的集合, \(i + 2 * n\) 代表 \(i\) 的天敌的集合.

若 \(A\) 与 \(B\) 同类, 则 bind(A, B), bind(A + n, B + n), bind(A + 2 * n, B + 2 * n).
若 \(A\) 吃 \(B\), 则 bind(A, B + 2 * n), bind(A + n, B), bind(A + 2 * n, B + n).

void solve() {
    int n, k;
    cin >> n >> k;
    DSU ds(n * 3);
    int ans = 0;
    while (k--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (x > n || y > n)
            ans++;
        else if (op == 1) {
            if (ds.root(x) == ds.root(y + n) || ds.root(x + n) == ds.root(y))
                ans++;
            else
                ds.bind(x, y), ds.bind(x + n, y + n), ds.bind(x + 2 * n, y + 2 * n);
        } else if (op == 2) {
            if (ds.root(x) == ds.root(y) || ds.root(x + 2 * n) == ds.root(y))
                ans++;
            else
                ds.bind(x + n, y), ds.bind(x, y + 2 * n), ds.bind(x + 2 * n, y + n);
        }
    }
    cout << ans << '\n';
}

DSU-并查集