Skip to main content

240.食物链

tip

原题链接：https://www.acwing.com/problem/content/242/

思路​

带权并查集

  • 本题因为不知道哪一类动物属于A，B，C的一种所以我们不考虑它的种类

  • 由于题目已知三类动物是环形的关系，也就是说知道两个的关系能确定第三个

  • 所以需要给并查集中每条边赋权，正好是一个环形的关系，所以能够想到使用模n同余的思想。

代码​

#include <iostream>

using namespace std;

const int N = 5e4 + 10;

int n, k, cnt = 0;
int p[N], d[N];

int find(int x ) {
    if (p[x] != x) {
        int t = find(p[x]);
        d[x] += d[p[x]]; // d[x]表示x到父节点的距离，d[p[x]]表示父节点到根节点的距离，所以这里求x到根节点之间的距离
        p[x] = t;
    }
    return p[x];
}

int main() {
    
    
    cin >> n >> k;
    
    for (int i = 1; i <= n; i++) p[i] = i;
    
    while (k --) {
        
        int ops, x, y;

        cin >> ops >> x >> y;

        if (x > n || y > n) cnt ++;
        else {
            int px = find(x), py = find(y);
            if (ops == 1) {
                if (px == py && (d[x] - d[y]) % 3) cnt ++;
                else if (px != py) {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            } else {
                if (px == py && (d[x] - d[y] - 1) % 3) cnt ++;
                else if (px != py) {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    cout << cnt << endl;
    return 0;
}