Uva(11396)(Claw Decomposition)

链接：https://vjudge.net/problem/UVA-11396
思路：二分图匹配，哎看不出来啊，说一下思路吧，如果确定某个点为爪点，那么它身边的三个点一定是附点，附点之间又不可能相连，所以附点连接的又一定是爪点，这不就是二分图匹配吗.........
代码：

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

const int maxn = 301;
vector<int> G[maxn];
int n;
int color[maxn];

bool bipatirate(int u){
for(int i=0;i<G[u].size();i++){
    int v = G[u][i];
    if(color[v]==color[u])return false;
    if(!color[v]){
    color[v] = 3-color[u];
    if(!bipatirate(v))return false;
    }
    }
    return  true;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
while(scanf("%d",&n)&&n){
    memset(color,0,sizeof(color));
    for(int i=0;i<n;i++)G[i].clear();
int a,b;
while(scanf("%d%d",&a,&b)&&(a||b)){
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
}
color[0] = 1;
if(bipatirate(0))printf("YES\n");
else printf("NO\n");
}
return 0;
}