题解：UVA11396 Claw Decomposition

· · 题解

做法

对于每一个爪，我们发现有 1 个点度为 3，剩下 3 个点度为 1，我们不妨将度为 3 的点当作根，度为 1 的点当作叶子，如下图： 当多个爪连在一起，我们就会发现，1 个根一定连着 3 个叶子，1 个叶子一定连着 3 个根，如下图：

所以我们就可以用 dfs 进行交替染色，如果在搜索过程中发现一个点既为根又为叶子，就说明该图不是爪图。

在学完二分图后我们也能发现在一个爪图中仅有根和叶子两个集合，所以本题也可以被视为一道关于二分图的判定的题目。

代码

注：由于本蒟蒻并没有 UVA 的号所以无法验证代码的正确性，仅供参考。

#include<cstdio>
#include<iostream>
using namespace std;
int n,m;
int a,b;
int num[1805],pre[1805],last[305],cnt;
int cntw,cntb;
int t[305],c[305];
int fla;
void ddxyz(){
    cnt=0;
    fla=0;
    for(int i=1;i<=n;i++){
        last[i]=0;
        t[i]=0;
        c[i]=0;
    }
}
void add(int x,int y){
    ++cnt;
    num[cnt]=y;
    pre[cnt]=last[x];
    last[x]=cnt;
}
void dfs(int xy,int col){
    t[xy]=1;
    c[xy]=col;
    if(col==1){
        cntw++;
    }
    else{
        cntb++;
    }
    if(col==1){
        col=2;
    }
    else{
        col=1;
    }
    for(int i=last[xy];i;i=pre[i]){
        if(t[num[i]]==0){
            dfs(num[i],col);
            if(fla==1){
                return ;
            }
        }
        else{
            if(col!=c[num[i]]){
                fla=1;
                return ;
            }
        }
    }
}
int main(){
    while(1){
        scanf("%d",&n);
        if(n==0){
            break;
        }
        ddxyz();
        while(1){
            scanf("%d%d",&a,&b);
            if(a==0&&b==0){
                break;
            }
            add(a,b);
            add(b,a);
        }
        for(int i=1;i<=n;i++){
            if(t[i]==0){
                cntw=0;
                cntb=0;
                dfs(i,1);
                if(fla==1){
                    printf("NO\n");
                    break;
                }
            }
        }
        if(fla==0){
            printf("YES\n");
        }
    }
    return 0;
}