首页 > 其他 > 详细

食物链

时间:2021-06-06 22:29:09      阅读:37      评论:0      收藏:0      [点我收藏+]

扩展域并查集

题目:

https://ac.nowcoder.com/acm/problem/16884

x是A,x+n是B,x+2n是C

#include<stdio.h>
const int maxn=150000;
int f[maxn];
int find(int x)
{
return x==f[x]?x:f[x]=find(f[x]);
}
void mix(int a,int b)
{
int fa=find(a);
int fb=find(b);
if(fa==fb)
return;
else
f[fa]=fb;
}
int main()
{
int n,k;
scanf("%d %d",&n,&k);
for(int i=1;i<=3*n;i++)
f[i]=i;
int d,x,y;
int ans=0;
while(k--)
{
scanf("%d %d %d",&d,&x,&y);
if(x>n||y>n)
{
ans++;
continue;
}
if(d==1)
{
if(find(x)==find(y+n)||find(x)==find(y+2*n))
ans++;
else
{
mix(x,y);
mix(x+n,y+n);
mix(x+2*n,y+2*n);
}
}
else
{
if(find(x)==find(y)||find(x)==find(y+2*n))
ans++;
else
{
mix(x,y+n);
mix(x+n,y+2*n);
mix(x+2*n,y);
}
}
}
printf("%d\n",ans);
}

 

食物链

原文:https://www.cnblogs.com/aacm/p/14856537.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!