题解 UVA11396 【Claw Decomposition】

2018-05-07 10:04:35


这套题我错了12遍。。。容我解释一下

其中八遍都是提交时发生未知错误。。所以大家千万不要冲动,发生错误了过一段时间再去提交,不要一直交。。。

还有4遍是真的被坑到了,一直没想到,看了网上的代码才知道,原来n=0的时候不用输出。。。。不用输出!!!

然后进入正题。。。

由于题目已经告诉了这个图是无向无环图,而且每个点的度都为3,每条边恰好属于一个爪。这样的话我们只用判断这个图是否为二分图即可。

代码如下

#include<cstdio> 
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,cnt=0,col[310];
int head[200000],nxt[200000],to[200000];
void addedge(int x,int y)
{
    cnt++;
    nxt[cnt]=head[x];
    head[x]=cnt;
    to[cnt]=y;
}
bool judge(int u)
{
    for(int i=head[u];i!=-1;i=nxt[i])
    {
        int v=to[i];
        if(col[v]==col[u]) return 0;
        else if(!col[v])
        {
            col[v]=3-col[u];
            if(!judge(v)) return 0;
        }
    }
    return 1;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        cnt=0;
        memset(col,0,sizeof(col));
        memset(head,-1,sizeof(head));
        while(1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(!x && !y) break;
            addedge(x,y);
            addedge(y,x);
        }
        if(n==0) continue;
        int f=1;
        for(int i=1;i<=n;i++)
            if(!col[i])
            {
                col[i]=1;
                if(!judge(i))
                {
                    f=0;
                    break;
                }
            }
        if(f) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}