AcWing 240. 【算法基础课】食物链    原题链接    中等

作者： 作者的头像   Conan15 ,  2022-07-27 18:45:43 ,  所有人可见 ,  阅读 1735

19


2

$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

笔记：
食物链.png

代码：

#include<bits/stdc++.h>
using namespace std;
int n, fa[150010], q, ans;
int get(int x){
    if(x == fa[x])return x;
    return fa[x] = get(fa[x]);
}
int main(){
    scanf("%d%d", &n, &q);
    for(int i = 1;i <= 3 * n; i++) fa[i] = i;
    int c, x, y;
    for(int i = 1;i <= q; i++){
        scanf("%d%d%d", &c, &x, &y);
        if(x > n || y > n || (c == 2 && x == y)){ ans++; continue; }
        if(c == 1 && (get(x) == get(y+n) || get(x+n) == get(y))){ ans++; continue; }
        if(c == 2 && (get(x) == get(y) || get(x) == get(y+n))){ ans++; continue; }
        if(c == 1){
            fa[get(x)] = get(y);
            fa[get(x+n)] = get(y+n);
            fa[get(x+2*n)] = get(y+2*n);
        }
        if(c == 2){
            fa[get(x+n)] = get(y);
            fa[get(x+2*n)] = get(y+n);
            fa[get(x)] = get(y+2*n);
        }
    }
    printf("%d\n", ans);
    return 0;
}

3 评论

用户头像
acwing_3927   1个月前         踩      回复

0-n存的是self，n-2n存的是吃的，2n到3n存的天敌

用户头像
weirdoZ   2023-02-27 11:04         踩      回复

牛啊 懂了

用户头像
光可遇   2023-02-16 21:57         踩      回复 
#include <iostream>
#include <algorithm>
using namespace std;
const int N=150010;
int q[N],ans=0;
int find(int x)
{
    if(q[x]!=x)q[x]=find(q[x]);
    return q[x];
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=3*n;i++)q[i]=i;
    for(int i=1;i<=q;i++)
    {
        int c,a,b;
        cin>>c>>a>>b;
        if(a>n||b>n||(c==2&&a==b)){ans++;continue;}
        if(c==1&&(find(a)==find(b+n)||find(a+n)==find(b))){ans++;continue;}
        if(c==2&&(find(a)==find(b)||find(a)==find(b+n))){ans++;continue;}
        if(c==1)
        {
            q[find(a)]==find(b);
            q[find(a+n)]==find(b+n);
            q[find(a+2*n)]==find(b+2*n);
        }
        if(c==2)
        {
            q[find(a+n)]==find(b);
            q[find(a)]==find(b+2*n);
            q[find(a+2*n)]==find(b+n);
        }

    }
    cout<<ans<<endl;

    return 0;
}

###大佬帮忙看看这个哪里不对

用户头像
冰中月   2022-07-27 22:07         踩      回复

你发了两遍一毛一样的？