POJ1182 食物链 【并查集变种】

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

挺简单的

N个元素扩展为 3*N个

i-A i-B i-C

A吃B吃C吃A

挑战程序设计的89面

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int N,K;
const int MAX_N=333333;
//并查集
int par[MAX_N];
int rank[MAX_N];//树的高度
void init(int n)
{for(int i=0;i<n;i++){par[i]=i;rank[i]=0;}
}
int find(int x)//
{if(par[x]==x)return x;elsereturn par[x]=find(par[x]);
}
//合并x和y所属的集合
void unite(int x,int y)
{x=find(x);y=find(y);if(x==y)return;if(rank[x]<rank[y])par[x]=y;else{par[y]=x;if(rank[x]==rank[y])rank[x]++;}
}
//判断x和y是否同属于一个集合
bool same(int x, int y)
{return find(x)==find(y);
}
int main()
{#ifndef ONLINE_JUDGEfreopen("G:/1.txt","r",stdin);freopen("G:/2.txt","w",stdout);#endifscanf("%d%d",&N,&K);init(3*N);int kind,a,b;int ans=0;for(int i=0;i<K;i++){scanf("%d%d%d",&kind,&a,&b);int x=a-1;int y=b-1;if(x<0||x>=N||y<0||y>=N){ans++;continue;}if(kind==1){if(same(x,y+N)||same(x,y+2*N)){ans++;continue;}unite(x,y);unite(x+N,y+N);unite(x+2*N,y+2*N);}else{if(same(x,y)||same(x+N,y+N)||same(x+2*N,y+2*N)||same(x,y+2*N)){ans++;continue;}unite(x,y+N);unite(x+N,y+2*N);unite(x+2*N,y);}}printf("%d\n",ans);return 0;
}

 

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

---