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

题目描述

有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;
}