【acwing】240. food chain

subject

Train of thought

How to merge different query sets , For the same kind （1） Come on ：

For different classes （2） Come on ：

Code 1

#include<iostream>
using namespace std;

const int N=50005;
int p[N],d[N];
int n,m;

int find(int x){
    // Record the distance to the root node 
    if(p[x]!=x){
    
        int t=find(p[x]);  
        d[x]+=d[p[x]];
        p[x]=t;
    }
    return p[x];
}

int main(){
    
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    
        p[i]=i;  // All parent nodes are themselves 
    }
    
    int res=0;
    while(m--){
    
        int t,x,y;
        cin>>t>>x>>y;
        if(x>n || y>n){
       //x,y Greater than n The scope of the , This sentence is a lie 
            res++;
        }else{
    
            int px=find(x);//x The root node 
            int py=find(y);//y The root node 
            
            if(t==1){
    //x and y It's the same kind 
                if(px==py && (d[x]-d[y])%3!=0){
      // In the same tree , The distance difference between two points %3 Not for 0, It means it's not the same kind 
                    res++;
                }else if(px != py){
     //x,y Not in the same tree 
                    p[px]=py;  //x The root node of is connected to y On the root node of 
                    d[px]=d[y]-d[x];
                }
            }else{
    //x eat y
                if(px==py && (d[x]-d[y]-1)%3!=0){
     //x,y In the same tree ,x Distance ratio y Freshman , namely (dx-dy-1)%3==0
                    res++; 
                }else if(px != py){
    //x,y Not in the same tree ,
                    p[px]=py;//x The root node of is connected to y On the root node of 
                    d[px]=d[y]+1-d[x];
                }
            }
        }
    }
    
    cout<<res<<endl;
    return 0;
}

Train of thought two

Union checking set ( Expanding domain )
This topic is mainly to open three expanded domains , That is, the natural enemy domain , Homogeneous domain , And predatory areas .

If x,y It's the same kind , however x Of Predatory domain Yes y, that
If x,y It's the same kind , however x Of Natural enemy territory Yes y, that
If x,y It's the same kind , however x Of Homogeneous domain Yes y, that

If x yes y The natural enemies of , however x Of Homogeneous domain There is y, that
If x yes y The natural enemies of , however x Of Natural enemy territory There is y, that
If x yes y The world of , however x Of Predatory domain There is y, that

Let's make the present X The predation domain of is X+N, At present X The natural enemy domain of is X+Ｎ+N

Code 2

// Let's make the present X The predation domain of is X+N, At present X The natural enemy domain of is X+Ｎ＋Ｎ
#include<iostream>
using namespace std;

const int N=50000*3+5;

int p[N];
int n,m;

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

int main(){
    
    cin>>n>>m;
    for(int i=1;i<=3*n;i++){
    
        p[i]=i;
    }
    
    int res=0;
    while (m -- ){
    
        int k,x,y;
        cin>>k>>x>>y;
        if(x>n || y>n){
    
            res++;
        }else if(k==1){
    //x and y similar 
            if(find(x)==find(y+n) || find(x)==find(y+n+n)){
    //x stay y In the predatory domain ,x stay y In the field of natural enemies 
                res++;
            }else{
    
                p[find(x)]=p[find(y)];  //x and y similar 
                p[find(x+n)]=p[find(y+n)];  //x Predatory domain and y Predatory domain of the same 
                p[find(x+n+n)]=p[find(y+n+n)];  //x Natural enemy domain and y The natural enemy domain of 
            }
        }else{
      //x yes y The natural enemies of 
            if(x==y || find(x)==find(y) || find(x)==find(y+n)){
     //x and y Is the same ,x and y It's the same kind ,x yes y The predator-prey area 
                res++;
            }else{
    
                p[find(x)]=p[find(y+n+n)]; //y Add... To your natural enemy domain x
                p[find(x+n)]=p[find(y)];  //x In the predator-prey domain y
                p[find(x+n+n)]=p[find(y+n)];  //x Natural enemy domain and y The predatory domain of is the same 
            }
        }
    }
    cout<<res<<endl;
    return 0;
}