首页 > 代码库 > POJ 1182 食物链（并查集拆点）
POJ 1182 食物链（并查集拆点）
【题目链接】 http://poj.org/problem?id=1182
【题目大意】
草原上有三种物种，分别为A,B,C
A吃B，B吃C，C吃A。
1 x y表示x和y是同类，2 x y表示x吃y
问给出的信息有几条是和前面相违背的
【题解】
之前这道题是用加权并查集做的，做的有些晕晕乎乎，现在换了种思路做就清晰很多了
将每个点拆点，比如x拆为，x-A，x-B，x-C
表示x属于A类，x属于B类，和x属于C类，
如果y和x属于同类，那么合并x-A和y-A，x-B和y-B，x-C和y-C
如果是x吃y的情况，那么合并x-A和y-B，x-B和y-C，x-C和y-A
也就是说将x属于A这种类型的条件作为节点进行并查集运算
就能很轻松地解决这种问题
【代码】
#include <cstdio>const int N=50010*3;int f[N],n,k,ans=0,op,x,y;void init(int n){for(int i=0;i<=n;i++)f[i]=i;}int sf(int x){return f[x]==x?x:f[x]=sf(f[x]);}bool Same(int x,int y){return sf(x)==sf(y);}bool Union(int x,int y){f[sf(x)]=sf(y);}int main(){ scanf("%d%d",&n,&k); init(3*n); for(int i=1;i<=k;i++){ scanf("%d%d%d",&op,&x,&y); if(--x<0||x>=n||--y<0||y>=n){ans++;continue;} if(op==1){ if(Same(x,y+n)||Same(x,y+2*n))ans++; else{Union(x,y);Union(x+n,y+n);Union(x+2*n,y+2*n);} }else{ if(Same(x,y)||Same(x,y+2*n))ans++; else{Union(x,y+n);Union(x+n,y+2*n);Union(x+2*n,y);} } }printf("%d\n",ans); return 0;}
POJ 1182 食物链（并查集拆点）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。