## Title Link

## Title Description

In the animal kingdom, there are three kinds of animals a, B and C. The food chain of these three kinds of animals forms an interesting ring. A eat B, B eat C, C eat a.

There are N animals, numbered 1-N. Every animal is one of a, B and C, but we don't know which one it is.

There are two ways to describe the food chain relationship of these N animals:

The first is "1 X Y", which means that X and Y are the same kind.

The second is "2 X Y", which means X eats Y.

For N animals, he said K sentences one by one in the above two ways, some of which are true and some are false. When a sentence satisfies one of the following three, it is a lie, otherwise it is the truth.

• the current words conflict with some of the real words in front, that is, lies

• in the current conversation, X or Y is larger than N, which is a lie

The current words mean that X eats X, which is a lie

Your task is to output the total number of lies according to the given N and K sentences.

## Title Solution

I used and looked it up

The idea of anti set is mainly applied

See notes for details.

1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 using namespace std; 5 6 const int maxn=50005; 7 int f[maxn*3],ans=0;//x For itself, x+n For prey x+n*2 Natural enemies 8 9 int find(int k){//lookup 10 if(f[k]==k) 11 return k; 12 return f[k]=find(f[k]); 13 } 14 15 void unionn(int x,int y){//merge 16 x=find(x); 17 y=find(y); 18 f[x]=y; 19 } 20 21 int main(){ 22 int n,k; 23 cin>>n>>k; 24 for(int i=1;i<=n*3;i++){ 25 f[i]=i; 26 } 27 for(int i=1;i<=k;i++){ 28 int judge,x,y; 29 cin>>judge>>x>>y; 30 if(x>n || y>n){ 31 ans++;//Out of scope, lies 32 continue; 33 } 34 if(judge==1){ 35 if(find(x+n)==find(y) || find(x+n*2)==find(y)){ 36 ans++;//It can't be the same as natural enemies and prey 37 continue; 38 } 39 unionn(x,y); 40 unionn(x+n,y+n); 41 unionn(x+n*2,y+n*2); 42 continue; 43 } 44 if(judge==2){ 45 if(x==y){ 46 ans++;//I eat myself 47 continue; 48 } 49 if(find(x)==find(y) || find(x+n*2)==find(y)){ 50 ans++;//I eat myself && Eat natural enemies 51 continue; 52 } 53 unionn(x+n*2,y+n); 54 unionn(x+n,y); 55 unionn(x,y+n*2); 56 continue; 57 } 58 } 59 cout<<ans; 60 return 0; 61 }