五行学说

· · 题解

题意

五行金木水火土中有“生”和“克”的关系，关系如下 共有 n 件物品， m 条关系，若关系为 s a b 代表 a 生 b ，若关系为 k a b 代表 a 克 b ，求出给定 m 个关系中错误的个数。

算法

并查集，带权并查集

带权并查集

在并查集原有树的基础上，给每个树的边一个权值，可用一个数组 fa[N] 表示这个点的祖先，用 v[N] 表示这个点到其父亲的边的边权

核心思路

处理多个数的关系时，我们通常会用并查集，对于克和生的关系，我们可以使用带权并查集来完成，我们用边权为 1 代表生，边权为 2 代表克，这样就可以在得到一对数及其之间的关系后先检验其是否在一个集合，若是在一个集合，那么只需要判断其关系是否是数据中所给，若是不在一个集合，表示他们之间的关系还没有确定，将他们合并为一个集合。

关键

在同一个集合中如何判断两个元素的关系呢？只需要求出两者之间的距离就可以！

当处理没有在同一个集合的元素时，如何将两个集合合并呢？传统集合只需要 fa[x]=y 而带边权的集合却需要将其中的 v[x] 更新，我们已知 a 和 b 之间的关系即 a 和 b 的距离，已知 a 到 x 的距离，b 到 y 的距离，我们设 a 和 b 的距离为 d 则 v[a]+v[x]-v[b]=d 即 v[x]=d+v[b]-v[a]

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

int n, m, ans, fa[N], v[N];
int find(int x) {
    if (fa[x] == x) return x;
    int t = find(fa[x]);
    v[x] = (v[fa[x]] + v[x]) % 5;
    fa[x] = t;
    return t;
}
int main() {
    for (int i = 1; i < N; i++) fa[i] = i;
    cin >> n >> m;
    char c;
    int a, b;
    for (int i = 1; i <= m; i++) {
        cin >> c >> a >> b;
        int x = find(a), y = find(b);
        if (x == y) {
            int d = (v[a] - v[b] + 10) % 5;
            if ((c == 'k' && d != 2) || (c == 's' && d != 1)) ans++;
        } else {
            fa[x] = y;
            int d = (c == 'k' ? 2 : 1);
            v[x] = (-v[a] + d + v[b] + 10) % 5;
        }
    }
    cout << ans << endl;
    return 0;
}