记录编号 |
570334 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[NOI 2001]食物链 |
最终得分 |
100 |
用户昵称 |
ムラサメ |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.041 s |
提交时间 |
2022-03-28 07:04:02 |
内存使用 |
2.81 MiB |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int fa[300005];
int n,k,ans;
int find(int x){
if(x!=fa[x]){
fa[x]=find(fa[x]);
}
return fa[x];
}
void merge(int x,int y){
int r1=find(fa[x]),r2=find(fa[y]);
fa[r1]=r2;
}
int main(){
freopen("eat.in","r",stdin);
freopen("eat.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int i=1;i<=3*n;++i){
fa[i]=i;
}
int x,y,w;
for(int i=1;i<=k;++i){
cin>>w>>x>>y;
if(x>n||y>n){
ans++;
continue;
}
if(w==1){
if(find(x+n)==find(y)||find(x+2*n)==find(y)){
ans++;
continue;
}
merge(x,y);
merge(x+n,y+n);
merge(x+2*n,y+2*n);
}
else{
if(w==2){
if(x==y){
ans++;
continue;
}
if(find(x)==find(y)||find(x+2*n)==find(y)){
ans++;
continue;
}
merge(x,y+2*n);
merge(x+n,y);
merge(x+2*n,y+n);
}
}
}
cout<<ans<<endl;
return 0;
}