社区讨论
20pts求助,一寒假没写题不会做了
P2024[NOI2001] 食物链参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mmagvxh9
- 此快照首次捕获于
- 2026/03/03 18:30 上周
- 此快照最后确认于
- 2026/03/04 09:24 7 天前
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4;
int n,k,x,y,ans;
int f[N],eat[N],ate[N];
//f为并查集,eat[a]=b表示a吃b,ate[a]=b表示b被a吃
char c;
inline void init(){
for(int i=1;i<=n;i++)
f[i]=eat[i]=ate[i]=i;
}inline int find(int x){
if(f[x]==x) return x;
return f[x]=find(f[x]);
}inline void merge(int x,int y){
f[find(x)]=find(y);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>k;init();
for(int i=1;i<=k;i++){
cin>>c>>x>>y;
if(x>n||y>n){
ans++;
continue;
}else{
if(c=='1'){
if(x==y) continue;
if(eat[f[x]]==f[y]||eat[f[y]]==f[x]){
ans++;
continue;
}merge(x,y);
}else{
if(f[x]==f[y]){
ans++;
continue;
}if(eat[x]==x) eat[x]=y;
else merge(eat[x],y);
if(ate[y]==y) ate[y]=x;
else merge(x,ate[y]);
}
}
}cout<<ans;
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...