[NOI 2001]食物連鎖

[NOI 2001]食物連鎖
問題の大意は必ず読めるが、どうすればいいかは問題だ.私の方法は権力を持ってセットを調べることです.まず、rと父(根)の関係を表す配列rをもう一つ追加することができます.コードを見ればわかります.

#include //a==fa[a]   0    a -> fa[a]  1   a 
using namespace std;  //      r     ，   0        ， 1        ， 2      。
int fa[100005],r[100005],ans,n,m;
int get(int x){
    if(fa[x]==x)    return x;
    int y=fa[x];//       
    fa[x]=get(fa[x]);//    
    r[x]=(r[y]+r[x])%3;//           
    return fa[x];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(;m--;){
        int c,x,y;
        scanf("%d%d%d",&c,&x,&y);
        if(x>n||y>n) ans++;
        else
        {
            int xx=get(x),yy=get(y);
            if(xx==yy){
                if(c==1&&r[x]!=r[y]) ans++;//             
                if(c==2&&(r[x]==r[y]||(r[y]+1)%3==r[x])) ans++;//      
            }
            else {
                fa[xx]=yy;//    
                if(c==1) r[xx]=(r[y]-r[x]+3)%3;
                else r[xx]=(r[y]-r[x]+2)%3;
            }
        }
    }
    printf("%d",ans);
    return 0;
}

実はもう一つの方法は、どうせ私たちはすべての動物がA、Bに属しているのかCに属しているのか分からないので、私たちはすべての状況について考えています(3倍の空間を開けます).1操作と仮定すると,入力されたxとyは,各種類のxとをつなぎ合わせて1つの集合(そして集合を調べる)となり,2操作であれば3つのケース:1,xがA yでB 2,xがB yでC 3,xがC yでAをそれぞれつなぎ合わせて矛盾を判断するのは簡単である.コードを見て

#include
using namespace std;
int fa[3*100005],n,m,ans;
int get(int x){
    return x==fa[x]? x:(fa[x]=get(fa[x]));//      
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=3*n;i++) fa[i]=i;
    for(;m--;){
        int c,x,y;
        scanf("%d%d%d",&c,&x,&y);
        if(x>n||y>n) ans++;//        
        else
        if(c==1){
            if(get(x+n)==get(y)||get(x)==get(y+n)) ans++;//  x y    y x      
            else fa[get(x)]=fa[get(y)],fa[get(x+n)]=fa[get(y+n)],fa[get(x+2*n)]=fa[get(y+2*n)];//       
        }
        else{
            if(get(x)==get(y)||get(x+n)==get(y)) ans++; //  x y   x y      
            else fa[get(x)]=fa[get(y+n)],fa[get(x+n)]=fa[get(y+2*n)],fa[get(x+2*n)]=fa[get(y)];//      +1
        }
    } 
    printf("%d",ans);
    return 0;
}

この問題をやり終えて、また調査集に対する理解が深まったような気がします.