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。

//与父节点的关系,0:同类,1:吃根节点,2:被根节点吃  

并查集的优势在于可以将所有类型的数据放在一个集合，通过数组r来表示各个元素与根节点的关系，同时每个元素访问根节点非常快（路径压缩），进而可以判断新来的两个元素关系与旧关系是否存在矛盾。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int NN=50005;

int n;

int p[NN]; //根节点

int r[NN]; //与父节点的关系,0:同类,1:吃根节点,2:被根节点吃

inline void get(int &x)

{

    char c=getchar();

    while (c<‘0‘ || c>‘9‘) c=getchar();

    x=c-‘0‘;

    c=getchar();

    while (c>=‘0‘ && c<=‘9‘) x=x*10+c-‘0‘,c=getchar();

}

int find(int x)

{

    if (p[x]!=x)

    {

        int t=p[x];

        p[x]=find(p[x]);

        r[x]=(r[x]+r[t])%3; //x与新父节点(根节点)的关系。ｒ［f］是ｘ的父节点，当进入／／递归以后，变成ｆｉｎｄ［f］，从而得到ｒ［f］的值（r[f]=r[f]+r[s]，s是根节点，ｒ［f］是全局变量），返回／／上一层递归的时候，旧r[x]仍然表示向量（f,x)(x与其旧根节点f相连的向量)，与新向量(s,f)相加得到s,x向量，即r[x]-r(s)=r[x]-0=r[x]

／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／        ani[now].parent = ani[ani[now].parent].parent;

        ani[now].relation = ( ani[now].relation + ani[now.parent].relation ) % 3;

        嗯，这样可以看到，( 儿子relation + 父亲relation ) % 3 = 儿子对爷爷的relation

        这就是路径压缩的节点算法，反应在向量图里：

按照右图的方向r(s,x)=r(s,f)+r(f,x)，t是x的旧父节点,s是t的新父节点，s是x新父节点

／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／／

    }

    return p[x];

}

int Union(int d,int x,int y)

{

    int fx=find(x);／／接入之前首先改变节点书上各个节点关系。即ＵＮＩＯＮ操作之后其实并不是所有节点的Ｒ［Ｘ］都是正确的

    int fy=find(y);

    p[fx]=fy;／／当把ＦＸ接到ＦＹ的后面时候，需要改变的是Ｘ与Ｘ的根节点的关系，即Ｒ［Ｘ］，在以后的ＦＩＮＤ过程中再来修改Ｘ下面各个节点的Ｒ值

    r[fx]=(r[y]-r[x]+2+d)%3; //

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

R(fx)-r(fy)=r(fx)-0=r(fx)=r(fy,fx)=r(fy,y)+r(y,x)+r(x,fx) 

其中r(x,fx)=r(fx)-r(x)=0-r(x)=-r(x)(此刻的r(x)针对的根节点是r1，而不是r2，这里看到迟点修改下面节点的意义了)

r(fy,y)=r(y)-r(fy),即r[fy]。

R(y,x)=d-1(加上2，防止出现负值)，d=1时，X,Y是同类，r(x,y)=0，表示两者一样的，当d=2，x吃y，r(y,x)=r(x)-r(y)=1，在后面的FIND过程中，X和Y的parent域都需要指向r2。假设y与r2同类，则x吃y也吃r2,因此r[y]=0,r[x]=1(d=1表示吃父节点)正好匹配。

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

}

int main()

{

    int d,x,y,k,cnt=0;

    scanf("%d%d",&n,&k);

    for (int i=1; i<=n; i++)

    {

        p[i]=i;

        r[i]=0;

    }

    while (k--)

    {

        get(d); get(x); get(y);

        if (x>n || y>n) cnt++;

        else if (d==2 && x==y) cnt++;

        else if (find(x)!=find(y)) Union(d,x,y);

//对于一个新来的d,x,y，如果xy不再一个并查集里，则无法判断该句话正确与否，因为说明是新来的一对（可能是其中的一个是第一次出现，或者两个都是，不能用find(x)==x || find(y)==y，判断，因为有可能find(x)=x,find(y)=x两个都在），在已经存在的集合里找不到这样的一对的，而要想找到矛盾必须与之前的比较菜可以，所以只好加进来，

        else if ((r[y]+d+2)%3!=r[x]) cnt++;

//这句话一定是在find(x)和find(y)之后的,因为find过后r[x]才是x与其根节点的关系，这里的意义是：如果x和y在同一个集合里，那么分两种情况：d=1，xy属于一类，因此r[x]=r[y]，因此 （r[y]+d+2)%3=r[x] ，d=2，x吃y，r[x]-r[y]=1，也满足（r[y]+d+2)%3=r[x]，即r[x]-r[y]=(d+2)%3

    }

    printf("%d\n",cnt);

    return 0;

}

UnionFind1182