codevs 1074食物链 并查集

本文主要是介绍codevs 1074食物链 并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

a和b之间有三种关系，a和b同类，a吃b，b吃a，用a+n表示a吃的，a+2*n表示吃a的。与关押犯人一样，但这里要影射出2种虚拟的才足以表示出关系。

#include<cstdio>
#include<iostream>
using namespace std;
int n,k,d,x,y;
int fa[200000];
int find(int x)
{return x==fa[x]?x:fa[x]=find(fa[x]);
}bool un(int x,int y)
{int px=find(x);int py=find(y);if(px==py)return false;fa[px]=py;return true;
}int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=3*n;i++) {fa[i]=i;}int ans=0;for(int i=0;i<k;i++) {scanf("%d%d%d",&d,&x,&y);if(x>n||y>n||(d==2&&x==y)){ans++;continue;}if(d==1) {if(find(x+n)==find(y)||find(y+n)==find(x)){ans++;continue;}un(x,y);un(x+n,y+n);un(x+2*n,y+2*n);}else {if(find(x)==find(y)||find(y+n)==find(x)){ans++;continue;}un(x+n,y);un(x,y+2*n);un(x+2*n,y+n);}}cout<<ans;return 0;
}

这篇关于codevs 1074食物链 并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---