本文主要是介绍poj_1182_并查集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述:
食物链,三种类型的动物。若输入没有与现实背离,则加入约束条件。若背离,则计算背离的输入有几组。
解题思路:
可以看出动物之间关系只有吃和被吃,以及同类两种关系。之前通过并a和MAX+b来标记不同类关系,可以借鉴这种思想,再标记a+IMAXb来标记被吃关系。那么,这种关系就能够表示了。要注意的是,每次的判断是否同类,是否吃和被吃的背离条件不能缺少。另外就是一组输入。
由于条件漏了两个,wa了好几次。唉。
代码:
#include <stdio.h>
#include <stdlib.h>
#define N 500000
#define MAX 100000
#define IMAX 200000
int set[N], cnt;
int find_set(int i)
{
if( i!= set[i] )
set[i] = find_set(set[i]);
return set[i];
}
void union_set(int x, int y)
{
int x1 = find_set(x);
int y1 = find_set(y);
set[x1] = set[y1];
}
main()
{
int id, words, x, y, op, i;
scanf("%d %d",&id, &words);
for(i=1;i<=IMAX+words;i++)
set[i] = i;
cnt = 0;
for(i=1;i<=words;i++){
scanf("%d %d %d",&op, &x, &y);
// printf("i:%d,words:%d\n",i,words);
if(op == 1){
if((x>id)||(y>id)|| x==0 || y==0){
cnt++;
//printf("fraud.\n");
}
else{
if(find_set(x) == find_set(y+MAX) || find_set(x) == find_set(y+IMAX) ||
find_set(y) == find_set(MAX+x) || find_set(y) == find_set(x+IMAX) ||
find_set(MAX+x) == find_set(y+IMAX) || find_set(x+IMAX) == find_set(y+MAX)){
cnt ++;
//printf("fraud.\n");
}
else{
union_set(x,y);
union_set(x+MAX,y+MAX);
union_set(x+IMAX,y+IMAX);
}
}
}else{ // x eat y
if(find_set(y)==find_set(x+MAX)||find_set(x) == find_set(y+IMAX) || find_set(MAX+y)==find_set(IMAX+x) ||