算法板子

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
int p[N], d[N];
int  n, k;
int find(int x) {
    if (p[x] != x) {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
};
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; ++i) p[i + 1] = i + 1;
    int res = 0;
    while (k--) {
        int x, y, z;
        cin >> z >> x >> y;
        if (x > n || y > n) {
            ++res;
            continue;
        }
        if (z == 1) {
            int rx = find(x), ry = find(y);
            if (rx == ry && (d[x] - d[y]) % 3) ++res;
            else if (rx != ry) {
                p[rx] = ry;
                d[rx] = d[y] - d[x];
            }
        }
        if (z == 2) {
            int rx = find(x), ry = find(y);
            if (rx == ry && (d[x] - d[y] - 1) % 3) ++res;
            else if (rx != ry) {
                p[rx] = ry;
                d[rx] = d[y] + 1 - d[x];
            }
        }
    }
    cout << res << endl;
    return 0;
};
本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/food-chain-union-find/
最后修改日期:2020年6月18日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。