AcWing 240. 食物链
原题链接
中等
作者:
你来die个头
,
2022-01-26 15:01:56
,
所有人可见
,
阅读 134
#include<bits/stdc++.h>
using namespace std;
const int N=150010;
int n,k;
int f[N];
int find(int x)
{
if(x!=f[x])f[x]=find(f[x]);
return f[x];
}
void ui(int x,int y)
{
int a=find(x),b=find(y);
f[a]=b;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n*3;i++)f[i]=i;
int ans=0;
while(k--)
{
int x,y,z;
scanf("%d%d%d",&z,&x,&y);
if(x>n||y>n){
ans++;continue;
}
if(z==1)
{
if(find(x+n)==find(y)||find(x+2*n)==find(y)){
ans++;continue;
}
ui(x,y);ui(x+n,y+n);ui(x+2*n,y+2*n);
}
else if(z==2)
{
if(x==y){
ans++;continue;
}
if(find(x)==find(y)||find(x+2*n)==find(y)){
ans++;continue;
}
ui(x,y+2*n);ui(x+n,y);ui(x+2*n,y+n);
}
}
printf("%d\n",ans);
}