【并查集】AcWing240. 食物链(并查集维护额外信息)

发布于 2022年 05月 19日 13:06

AcWing240. 食物链


题解

(2->1代表1吃2)
轻易可知,该食物链成一个环,只要得知该环中两条边,即可推出第三条边
将所有点存储在一个集合中,集合的边表示结点之间的关系,利用点到根节点的距离判断种类,故我们需要额外维护一个保存到父节点距离的数组。

路径压缩:还是将父节点直接改为根节点,距离从到父节点距离改为到根节点的距离。

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 50010;

int p[N], d[N];

int find(int x)
{
    if(p[x] != x)
    {
        int t = p[x];
        p[x] = find(p[x]);
        d[x] += d[t];
    }
    return p[x];
}

int main()
{
    int n, m, t, x, y;
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; ++i) p[i] = i;
    
    int res = 0;
    while (m -- )
    {
        scanf("%d%d%d", &t, &x, &y);
        if(x > n || y > n) res ++ ;
        else
        {
            int px = find(x), py = find(y);
            if(t == 1)
            {
                if(px == py && (d[x] - d[y]) % 3) res ++ ; //在同一个集合中余数不同为假话
                else if(px != py)//不在一个集合中,即两点没有确立关系,默认为真,开始确立关系
                {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else 
            {
                if(px == py && (d[x] - d[y] - 1) % 3 ) res ++ ;
                else if(px != py)
                {
                    p[px] = py;
                    d[px] = d[y] - d[x] + 1;
                }
            }
        }
    }
    printf("%d\n", res);
    return 0;
}

推荐文章