洛谷P2024-食物链-题解

【NOI2001】 食物链

题目描述

动物王国中有三类动物 $A,B,C$，这三类动物的食物链构成了有趣的环形。$A$ 吃 $B$，$B$ 吃 $C$，$C$ 吃 $A$。

现有 $N$ 个动物，以 $1 \sim N$ 编号。每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 $N$ 个动物所构成的食物链关系进行描述：

• 第一种说法是 1 X Y，表示 $X$ 和 $Y$ 是同类。
• 第二种说法是 2 X Y，表示 $X$ 吃 $Y$。

此人对 $N$ 个动物，用上述两种说法，一句接一句地说出 $K$ 句话，这 $K$ 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

• 当前的话与前面的某些真的话冲突，就是假话；
• 当前的话中 $X$ 或 $Y$ 比 $N$ 大，就是假话；
• 当前的话表示 $X$ 吃 $X$，就是假话。

你的任务是根据给定的 $N$ 和 $K$ 句话，输出假话的总数。

输入格式

第一行两个整数，$N,K$，表示有 $N$ 个动物，$K$ 句话。

第二行开始每行一句话（按照题目要求，见样例）

输出格式

一行，一个整数，表示假话的总数。

样例 #1

样例输入 #1

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

样例输出 #1

3

提示

对于全部数据，$1\le N\le 5 \times 10^4$，$1\le K \le 10^5$。

P2024 [NOI2001] 食物链 - 洛谷

思路

这题用到了一种叫种类并查集的数据结构。开一个三倍长的并查集，代表三种不同的物种，然后每次判断是否能合并，如果不能合并，则说明是假话。

C++代码

#include <iostream>
#include <vector>
#include <numeric>

template<typename T>
class UnionFindSet {

    std::vector<T> trees, size;
public:
    explicit UnionFindSet(T len) : trees(len << 1), size((len << 1), 1) {
        std::iota(trees.begin(), trees.begin() + len, len);
        std::iota(trees.begin() + len, trees.end(), len);
    }

    T find(const T &x) {
        return trees[x] == x ? x : trees[x] = find(trees[x]);
    }

    void unite(const T &x, const T &y) {
        T &&fx = find(x), &&fy = find(y);
        if (fx == fy) return;
        if (size[fx] < size[fy]) std::swap(fx, fy);
        trees[fy] = fx;
        size[fx] += size[fy];
    }

    void erase(const T &x) {
        --size[find(x)];
        trees[x] = x;
    }

    void move(const T &x, const T &y) {
        T &&fx = find(x), &&fy = find(y);
        if (fx == fy) return;
        trees[x] = fy;
        --size[fx], ++size[fy];
    }

    bool isSameSet(const T &x, const T &y) {
        return find(x) == find(y);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie();
    int n, k, opt, x, y, ans = 0;
    std::cin >> n >> k;
    UnionFindSet<int> ufs(3 * n + 3);
    auto getTheDead = [&](const int &x) { return x + n; };
    auto getKiller = [&](const int &x) { return x + 2 * n; };
    auto isKilled = [&](const int &killer, const int &theDead) {
        return ufs.find(getKiller(theDead)) == ufs.find(killer);
    };
    for (int i = 0; i < k; ++i) {
        std::cin >> opt >> x >> y;
        if (x > n or y > n or (opt == 2 and x == y)) {
            ++ans;
            continue;
        }
        if (opt == 1) {
            if (isKilled(x, y) or isKilled(y, x)) {
                ++ans;
                continue;
            }
            ufs.unite(x, y);
            ufs.unite(getTheDead(x), getTheDead(y));
            ufs.unite(getKiller(x), getKiller(y));
            continue;
        }
        if (ufs.isSameSet(x, y) or isKilled(y, x)) {
            ++ans;
            continue;
        }
        ufs.unite(x, getKiller(y));
        ufs.unite(getTheDead(x), y);
        ufs.unite(getKiller(x), getTheDead(y));
    }
    std::cout << ans;
    return 0;
}