食物链

Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u

Description

动物王国中有三类动物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

第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。

Output

只有一个整数，表示假话的数目。

Sample Input

Sample Output

3

//网上查并查集的时候看到的，说是一道经典题。看了两个资料。
链接如下：通俗易懂的并查集
          飘过的小牛
首先集合中的每个点与它的根结点有如下关系relation：
tree.[a]relation=0表示与根节点同类；
tree.[a]relation=1表示它吃根结点；
tree.[a]relation=2表示它被结点吃；
接下来是判断a和b的关系，我发的两个链接里讲的很清楚，我就简单复述一下：
在p=tree.[a]和q=tree[b]即p、q为a、b的根节点的情况下：
（1）若p！=q，则说明此时a，b无关系，则关于他们的判断都是正确的，然后将p合并于q，合并后p的relation必然会改变，公式为：tree[p].relation = (tree[b].relation - tree[a].relation + 2 + d) % 3（d为题中D）；
（2） 若p=q，说明a，b之间已经有关系了。那么久判断语句是否是正确的，同样利用式子：if ( (tree[b].relation + d + 2) % 3 != tree[a].relation )，满足则为错误的；

有疑问的即是“飘过的小牛”的向量思维模式，尚未理解；
源代码如下：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int sum;
struct node{
int parent;
int relation;
}tree[50010];

int Find(int x)
{
     int temp_p;
 if (tree[x].parent != x)  // 因为路径压缩，该结点的与根结点的关系要更新(因为前面合并时可能还没来得及更新).
 {
    temp_p = tree[x].parent;  tree[x].parent = Find(tree[x].parent);  // x与根结点的关系更新(因为根结点变了)，此时的temp_p为它原来子树的根结点.
    tree[x].relation = (tree[x].relation + tree[temp_p].relation) % 3; }
    return tree[x].parent;
}
/*为什么过不了？
void Merge (int a,int b,int p,int q,int d){

p=Find(a);
q=Find(b);
if(p!=q)
{
    tree[p].parent=q;
    tree[p].relation =(tree[b].relation-tree[a].relation+3+(d-1))%3;
}
 else if (tree[b].relation+(d-1)+2%3!=tree[a].relation)
    sum++;

}*/

int main()
{   int n,k;
    int a,b,d,q,p;
    sum=0;
    scanf("%d %d",&n,&k);
    for (int i=1;i<=n;++i)
    {
        tree[i].parent=i;
        tree[i].relation=0;
    }
   for (int i=1;i<=k;++i)
   {
       scanf("%d %d %d",&d,&a,&b);
      // Merge(a,b,p,q,d);
     if(a > n || b > n) //条件2
        {
            sum++;
            continue;
        }
        if(d == 2 && a == b) //条件3
        {
            sum++;
            continue;
        }
        p = Find(a);
        q = Find(b);
        if(p != q) // 合并
        {
            tree[q].parent = p;
            tree[q].relation = (3 + (d - 1) +tree[a].relation - tree[b].relation) % 3;
        }
        else
        {
            if(d == 1 && tree[a].relation != tree[b].relation)
            {
                sum++;
                continue;
            }
            if(d == 2 && ((3 - tree[a].relation + tree[b].relation) % 3 != d - 1))
            {
                sum++;
                continue;}
        }
   }
   printf("%d
",sum);
    return 0;
}

View Code