P2024 [NOI2001]食物链

佚名 6年前 (2019-05-14) 随笔 1058人围观抢沙发百度已收录

第一种说法是“1 X Y”，表示 X 和 Y 是同类。

第二种说法是“2 X Y”，表示 X 吃 Y 。

根据这句话可以看出来这是一个种类并查集

种类并查集通常数组要开大一倍

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

再根据这句话判断一下是否是假话如果是假话就 ans ++ 就可以了。

最后输出ans

// web :
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline LL read () { LL res = 0 ;int f (1) ;char ch = getchar ();
    while (!isdigit(ch)) { if (ch == '-') f = -1 ;ch = getchar();}
    while (isdigit(ch)) res = (res << 1) + (res << 3) + (ch ^ 48) ,ch = getchar(); return res * f ;
}
const int N = 50000+10 ;
int n,k;
int ans = 0 ;
int fa[N*3];
inline int get(int x) {
    if (x == fa[x]) return x;
    return fa[x] = get(fa[x]);
}
signed main () {
    n=read(); k=read();
    for(register int _=1;_<=n*3;_++) fa[_]=_;
    for(register int _=1;_<=k;_++) {
        int num=read(),x=read(),y=read();
        if(x>n or y>n or (num == 2 and x == y)){
            ans ++ ; continue ;
        }
        if(num == 1 and (get(x) == get(y+n) or get(x+n) == get(y))){
            ans ++ ; continue ;
        }
        if(num == 2 and (get(x) == get(y) or get(x) == get(y+n))) {
            ans ++ ; continue ;
        }
        if(num == 1) {
            fa[get(x)] = get(y) ;
            fa[get(x+n)] = get(y+n) ;
            fa[get(x+(n<<1))] = get(y+(n<<1));
        }
        else {
            fa[get(x+n)] = get(y) ;
            fa[get(x+(n<<1))] = get(y+n) ;
            fa[get(x)] = get(y+(n<<1)) ;
        }
    }
    cout << ans << endl ;
    return 0;
}