题目链接:https://vjudge.net/contest/166461#problem/A
题意:
给定一个图,特点是每个点的度都是3,求是不是原图可以分解为全部鸡爪;每条边只属于一个鸡爪;
分析:
每一个鸡爪的根对应三个其他的顶点,但是这三个点不能再作为鸡爪的根了,
这样,两个鸡爪根就不能直接相连,这就是二分图染色,其中作为根的在一边,作为附属点的另一边;
#include <bits/stdc++.h> using namespace std; const int maxn = ;
vector<int> G[maxn];
int color[maxn]; bool bipartite(int u) {
for(int i=;i<G[u].size();i++) {
int v = G[u][i];
if(color[v]==color[u])
return false;
if(!color[v]) {
color[v] = - color[u];
if(!bipartite(v)) return false;
}
}
} int main()
{
int n;
while(scanf("%d",&n),n) {
memset(color,,sizeof(color)); for(int i=;i<=n;i++)
G[i].clear();
int u,v;
while(scanf("%d%d",&u,&v)) {
if(u==&&v==)
break;
G[u].push_back(v);
G[v].push_back(u);
} color[] = ;
if(bipartite())
puts("YES");
else puts("NO"); }
return ;
}