poj1182:食物链

《挑战程序设计竞赛》——并查集

题目描述

有n个动物,属于A,B,C三个种类,A吃B,B吃C,C吃A,编号为1~n,给定k句话,求假话的个数

两种说法

  • 1 x y:x和y同类
  • 2 x y:x吃y

假话

  • 当前的话与前面的某些真的话冲突,就是假话
  • 当前的话中X或Y比N大,就是假话
  • 当前的话表示X吃X,就是假话

分析

并查集应用

不是简单的同组关系的并查集,涉及A,B,C三类的同类关系

对于每一个动物i,建立三个对象i-A,i-B,i-C,分别表示i属于A类,i属于B类和i属于C类。维护3*n的并查集,对于每句话进行如下维护

  • x和y同类:合并(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)

在合并之间需要先检查这句话是否是真话

简单来说,维护3*n的并查集,其实是将类别关系放在同一个并查集中考虑,即对于动物i同时考虑其属于A,B,C三个类别的情况。此外,在同一个组中(经过合并)的元素表示这两个元素之间存在某种关系,具体关系可根据其所属类别来进行判断。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 5E4 + 10;
int father[3*MAXN];     //并查集
int height[3*MAXN];     //并查集高度

//并查集初始化
void Init(){
    for (int i = 1; i <= 3*MAXN; ++i) {
        father[i] = i;
        height[i] = 0;
    }
}

//查找+路径压缩
int Find(int x){
    if(x != father[x]){
        father[x] = Find(father[x]);
    }
    return father[x];
}

//合并操作
void Unite(int x, int y){
    x = Find(x);
    y = Find(y);
    if(x != y){
        if(height[x] < height[y]){          //小树并到大树上,高度不变
            father[x] = y;
        }
        else{
            father[y] = x;
            if(height[x] == height[y]){     //两树相同,合并后高度+1
                height[x]++;
            }
        }
    }
    return;
}

//判断x,y是否在同一组
bool Same(int x, int y){
    if(Find(x) == Find(y)){
        return true;
    }
    else{
        return false;
    }
}

int main(){
    int n, k;
    int d, x, y;
    int ans = 0;
    Init();
    scanf("%d%d", &n, &k);
    for (int i = 0; i < k; ++i) {
        scanf("%d%d%d", &d, &x, &y);

        //不正确编号
        if(x < 1 || y < 1 || x > n || y > n){
            ++ans;
            continue;
        }
        
        //x和y同类
        if(d == 1){
            if(Same(x, y+n) || Same(x, y+2*n)){
                ++ans;
            }
            else{
                Unite(x, y);
                Unite(x+n, y+n);
                Unite(x+2*n, y+2*n);
            }
        }
        else{   //x吃y
            if(Same(x, y) || Same(x, y+2*n)){
                ++ans;
            }
            else{
                Unite(x, y+n);
                Unite(x+n, y+2*n);
                Unite(x+2*n, y);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

上一篇:Github api【Restful接口规范】


下一篇:Java中的二叉树(Peter),java语言入门基础