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

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;}