本文出自：http://blog.csdn.net/svitter
动物王国中有三类动物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），输出假话的总数。
Input
Output
Sample Input
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
Sample Output
3
//author: svtter
//
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#define INF 0xffffff
using namespace std;
const int MAXN = 150010;
int root[MAXN];
int n, k;
int n3;
void init()
{
n3 = 3*n;
for(int i = 0; i <= n3; i++)
root[i] = i;
}
int getRoot(int i)
{
if(i == root[i])
return i;
return root[i] = getRoot(root[i]);
}
int a, b;
void Merge(int i, int j)
{
a = getRoot(i);
b = getRoot(j);
if(a == b)
return;
root[a] = b;
}
bool jud(int i, int j)
{
return getRoot(i) == getRoot(j);
}
int main()
{
int i;
int r, t1, t2;
int n2;
int fal;
scanf("%d%d", &n, &k);
init();
n2 = n*2;
fal = 0;
for(i = 0; i < k; i++)
{
scanf("%d %d %d", &r, &t1, &t2 );
if(t1 > n || t2 > n
|| jud(t2, t1+n) || jud(t2+n ,t1+n2) || jud(t2+n2, t1))
{
fal++;
continue;
}
if(r == 2)
{
if(jud(t1, t2) || jud(t1+n, t2+n) || jud(t1+n2, t2+n2))
fal++;
else
{
Merge(t1, t2+n);
Merge(t1+n, t2+n2);
Merge(t1+n2, t2);
}
}
else
{
if(jud(t1, t2+n) || jud(t1+n, t2+n2) || jud(t1+n2, t2))
fal++;
else
{
Merge(t1, t2);
Merge(t1+n2, t2+n2);
Merge(t1+n, t2+n);
}
}
}
printf("%d\n", fal);
return 0;
}
POJ1182 食物链 (并查集）*新方法,布布扣,bubuko.com
原文：http://blog.csdn.net/svitter/article/details/38299373