P2024 [NOI2001]食物链
题意
略(中文)
思路
一道典型的扩展域并查集,我们开三倍数组,(1,n)记录同类域,(n+1,2n)记录捕食域,(2n+1,3*n)记录天敌域,分析各个域的关系,当x,y为同类时x的捕食域肯定不能是y,y的捕食域肯定不能是x,当x,y为捕食关系时(x吃y),此时x和y不能在同类域中,y的捕食域不能是x.
代码
#include<bits/stdc++.h>
using namespace std
;
const int maxn
=5e4+10;
int fa
[maxn
*3];
int find(int x
){
if(x
!=fa
[x
]) return fa
[x
]=find(fa
[x
]);
else return x
;
}
void merge(int x
,int y
){
x
=find(x
),y
=find(y
);
if(x
!=y
) fa
[x
]=y
;
}
int main(){
int n
,m
;
scanf("%d%d",&n
,&m
);
for(int i
=1;i
<=3*n
;i
++) fa
[i
]=i
;
int ans
=0;
for(int i
=1;i
<=m
;i
++){
int x
,y
,op
;scanf("%d%d%d",&op
,&x
,&y
);
if(x
>n
||y
>n
) {
ans
++;continue;
}
if(op
==1){
if(find(x
+n
)==find(y
)||find(x
)==find(y
+n
)) ans
++;
else {
merge(x
,y
);
merge(x
+n
,y
+n
);
merge(x
+2*n
,y
+2*n
);
}
}
else {
if(find(x
)==find(y
)||find(y
+n
)==find(x
)) ans
++;
else {
merge(x
+n
,y
);
merge(x
+2*n
,y
+n
);
merge(x
,y
+2*n
);
}
}
}
printf("%d\n",ans
);
}
