AcWing 240. 食物链

食物链 - 并查集

#include <iostream>

using namespace std;
const int N = 1e6 + 10;
int n, m;
int p[N], d[N];
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(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) p[i] = i;
    int res = 0;
    while(m--){
        int t, x, y;
        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] + 1 - d[x];
		        }
            }
        }
    }
    printf("%d\n", res);
    return 0;
}

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

// 余1：可以吃根节点
// 余2：可以被根节点吃
// 余0：与根节点是同类

int n, m;
int p[N], d[N];
// p是并查集的father d是维护的距离 用m来表示说话的个数

int find(int x){
    if(p[x] != x){
        int t = find(p[x]);
        //所以需要用一个变量来存下来
        d[x] += d[p[x]];//然后先让d[x]更新成d[p[x]]
        // p[x] = find(p[x]);//不可以这么写 因为赋完值之后p[x]就是存的根节点即find(p[x])了 所以要在赋值之前存下来
        p[x] = t;//在这之后再把p[x]更新成t就可以了
    }
    
    return p[x];
}

int main(){
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i++) p[i] = i;
    //初始化值 因为全局变量d本来就是0所以不需要初始化
    
    int res = 0; //res 是当前讲话的个数
    while(m--){
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        if(x > n || y > n) res ++;
        else{
            int px = find(x), py = find(y);//这里先把 x 和 y 的根节点找出来 px表示的是x的根节点 py表示的是y的根节点
            if(t == 1){
                if(px == py && (d[x] - d[y]) % 3) res ++;//说明x和y在一个树上
                else if(px != py){
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }//(d[x] + ? - d[y]) % 3 = 0 即 ? = d[y] - d[x]
            }
            else{
                if(px == py && (d[x] - d[y] - 1) % 3) res++;
                else if(px != py){//x 和 y不在一个集合里面
                    //(d[x] + ? - d[y] - 1 = 0) 即 ? = d[y] + 1 - d[x];
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    
    printf("%d\n", res);
    return 0;
}

![[Pasted image 20221220154424.png]]

# 第 84 行为什么 d [px] = d [y] - d [x]