Food chain (day 79)

1： subject

 There are three kinds of animals in the animal kingdom  A,B,C, The food chain of these three kinds of animals forms an interesting ring .

A  eat  B,B  eat  C,C  eat  A.

 existing  N  Animals , With  1∼N  Number .

 Every animal is  A,B,C  One of the , But we don't know which one it is .

 There are two ways of saying it  N  Describe the food chain of animals ：

 The first is  1 X Y, Express  X  and  Y  It's the same kind .

 The second is  2 X Y, Express  X  eat  Y.

 This man is right  N  Animals , Use the two statements above , Say... Sentence by sentence  K  Sentence , this  K  Some sentences are true , Some are fake .

 When a sentence satisfies one of the following three , This is a lie , Otherwise, it's the truth .

 The current words conflict with some of the real words in front , It's a lie ;
 In the current conversation  X  or  Y  Than  N  Big , It's a lie ;
 The current words mean  X  eat  X, It's a lie .
 Your task is based on the given  N  and  K  Sentence , The total number of output lies .

 Input format 
 The first line is two integers  N  and  K, Separated by a space .

 following  K  Each row is three positive integers  D,X,Y, Separate the two numbers with a space , among  D  The type of statement .

 if  D=1, said  X  and  Y  It's the same kind .

 if  D=2, said  X  eat  Y.

 Output format 
 There's only one whole number , The number of lies .

 Data range 
1≤N≤50000,
0≤K≤100000
 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
 

2： Code implementation

#include<iostream>
using namespace std;
const int N=1000010;

int n,m;
int p[N],d[N];

int find(int x)
{
    
    if(p[x]!=x)
    {
    
        int t=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=t;
    }
    return p[x];
}

int main()
{
    
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)p[i]=i;
    
    int res=0;
    while (m -- ){
    
        int t,x,y;
        scanf("%d%d%d",&t,&x,&y);
        
        if(x>n || y>n)res++;
        else 
        {
    
            int px=find(x),py=find(y);
            if(t==1)
            {
    
                if(px==py && (d[x]-d[y])%3)res++;
                else if(px!=py)
                {
    
                    p[px]=py;
                    d[px]=d[y]-d[x];
                }
            }
            else 
            {
    
                if(px==py && (d[x]-d[y]-1)%3)res++;
                else if(px!=py)
                {
    
                    p[px]=py;
                    d[px]=d[y]+1-d[x];
                }
            }
        }
    }
    printf("%d\n",res);
    return 0;
}