POJ1182——食物链（种类并差集）

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

非常经典的并查集。

其实关键还是要找到各个种类之间的转化关系，其实枚举找规律就可以。一开始的时候把关系式推错了，所以一直WA。

还有这题比较坑的地方是只能单组数据，不能写成!=EOF

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#define INF 0x7fffffff
using namespace std;
int fa[100001];
int rel[100001];// 0 同类 ，1吃父亲 ，2被父亲吃
int Find(int x)
{if(x==fa[x]) return x;else{int root=Find(fa[x]);rel[x]=(rel[x]+rel[fa[x]])%3;return fa[x]=root;}
}
int main()
{int n,k,i;int x,y,v;scanf("%d%d",&n,&k);{int cnt=0;for(i=1;i<=n;i++)fa[i]=i,rel[i]=0;for(i=0;i<k;i++){scanf("%d%d%d",&v,&x,&y);//if(v==1&&x==y) continue;if(v==2&&x==y||x>n||y>n) {cnt++;continue;}int ax=Find(x);int ay=Find(y);if(ax!=ay){fa[ax]=ay;rel[ax]=(rel[y]-rel[x]+v+2)%3;}else{if((rel[x]-rel[y]+3)%3!=v-1) cnt++;}}cout<<cnt<<endl;}return 0;
}

这篇关于POJ1182——食物链（种类并差集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---