P2024 [NOI2001]食物链[扩展域并查集]

大水题一道啊，几分钟切掉。

还是扩展域，每个点拆3个点，之间连边表示有关系（即捕食关系）。然后随便判定一下就好了，不难，毕竟NOI上古题目。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<queue>
 7 #define dbg(x) cerr<<#x<<" = "<<x<<endl
 8 #define ddbg(x,y) cerr<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<endl
 9 using namespace std;
10 typedef long long ll;
11 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;}
12 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;}
13 template<typename T>inline T _min(T A,T B){return A<B?A:B;}
14 template<typename T>inline T _max(T A,T B){return A>B?A:B;}
15 template<typename T>inline T read(T&x){
16     x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
17     while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
18 }
19 const int N=50000+7;
20 int fa[N<<2],n,m,x,y,c,cnt;
21 inline int Get(int x){return fa[x]^x?fa[x]=Get(fa[x]):x;}
22 
23 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);
24     read(n),read(m);
25     for(register int i=1;i<=n*3;++i)fa[i]=i;
26     for(register int i=1;i<=m;++i){
27         read(c),read(x),read(y);
28         if(x>n||y>n){++cnt;continue;}
29         if(c==1){
30             if(Get(x)==Get(y+n)||Get(x)==Get(y+n+n)){++cnt;continue;}
31             fa[Get(x)]=Get(y),fa[Get(x+n)]=Get(y+n),fa[Get(x+n+n)]=Get(y+n+n);
32         }
33         else{
34             if(Get(x)==Get(y)||Get(x)==Get(y+n+n)){++cnt;continue;}
35             fa[Get(x)]=Get(y+n),fa[Get(x+n)]=Get(y+n+n),fa[Get(x+n+n)]=Get(y);
36         }
37     }
38     printf("%d
",cnt);
39     return 0;
40 }