题解 UVA11396 【Claw Decomposition】

这套题我错了12遍。。。容我解释一下 其中八遍都是提交时发生未知错误。。所以大家千万不要冲动，发生错误了过一段时间再去提交，不要一直交。。。 还有4遍是真的被坑到了，一直没想到，看了网上的代码才知道，原来n=0的时候不用输出。。。。不用输出！！！ 然后进入正题。。。 由于题目已经告诉了这个图是无向无环图，而且每个点的度都为3，每条边恰好属于一个爪。这样的话我们只用判断这个图是否为二分图即可。 代码如下 ```cpp #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; } ```