题目地址:http://poj.org/problem?id=1182

题目大意

动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。

现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。

有人用两种说法对这N个动物所构成的食物链关系进行描述:

第一种说法是”1 X Y”,表示X和Y是同类。

第二种说法是”2 X Y”,表示X吃Y。

此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。

  1. 当前的话与前面的某些真的话冲突,就是假话;
  2. 当前的话中X或Y比N大,就是假话;
  3. 当前的话表示X吃X,就是假话。

你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。

思路

经典并查集题目。。并查集是维护“同一组”的数据结构,那么对每个动物创建三个元素$i-A, i-B, i-C$,可建立$3\times N$大小的并查集。

$i-x$表示$i$属于$x$。

并查集同一组的所有元素表示的情况都同时发生。

由于每个动物所在的种类是不确定的,所以当给出消息判断的时候,需要考虑$i$在$A, B, C$三种情况,那么将三种情况都合并起来即可减少判断量。即

情况一

unite(x, y); // 当x和y都在A组
unite(x+N, y+N); // 当x和y都在B组
unite(x+2*N, y+2*N); // 当x和y都在C组

情况二

unite(x, y+N); // 表示A的x吃B的y
unite(x+N, y+2*N); // 表示B的x吃C的y
unite(x+2*N, y); // 表示C的x吃A的y

AC代码

/*************************************************************************
    > File Name: 1182.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-11-10 二 17:58:44 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
int par[50000*3+10]; // 分为x-A, x-B, x-C三组,分别表示x属于A, B, C
// 并查集每一个组里的所有元素代表的情况都同时发生或者不发生。

void init(int N) {
    for(int i=1; i<=3*N; ++i) par[i] = i;
}
int find(int x) {
    return x==par[x]?x:par[x]=find(par[x]);
}
bool same(int x, int y) {
    return find(x) == find(y);
}
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x!=y)
        par[x] = y;
}


int main()
{
#ifdef Oj
    freopen("1182.in", "r", stdin);
#endif
    int N, K; // 动物编号, 条件数量
    scanf("%d%d",&N,&K); // 被cin/cout卡死了。。
    init(N);
    int pre, x, y;
    int ans = 0;
    while(K--) {
        scanf("%d%d%d", &pre, &x, &y);
        if(x<1 || x>N || y<1 || y>N) { // 范围错误
            ++ans;
            continue;
        }
        if(pre == 1) {
            if(same(x, y+N) || same(x, y+2*N)) // 当x属于A, 则y属于B或C都是异类,无需考虑x属于B或者C,因为下面合并的时候将x属于A, B, C都考虑进去了
                ++ans;
            else {
                // 以下考虑了三种情况,当x分别属于A, B, C时,将y分别和x放在一起
                unite(x, y);
                unite(x+N, y+N);
                unite(x+2*N, y+2*N);
            }
        }
        else {
            if(same(x, y) || same(x,y+2*N)) ++ans; // 当x, y同类,或者属于A的x吃了C的y,则为假话
            else {
                unite(x, y+N); // A的x吃B的y
                unite(x+N, y+2*N); // B的x吃C的y
                unite(x+2*N, y); // C的x吃A的y
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}