uva 11396（二分图判定）

题意：这道题主要是定义了一个交叫爪子的图：

然后他会给你一个每个结点度数都是三的无向图。问你能否能否拆成爪子图。（就是分成若干个子图，原图中的每条边都只能在一张子图中出现一次，点可以重复出现）。

思路：这道题我们可以画几个推理一下，会发现一个结论当且仅当图是而分图的时候是可以的，然后剩下来的就是染色判定了。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#define MP(a, b) make_pair(a, b)
#define PB(a) push_back(a)

using namespace std;

typedef long long ll;
typedef pair<int ,int> pii;
typedef pair<unsigned int, unsigned int> puu;
typedef pair<int ,double> pid;
typedef pair<ll, int> pli;

const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int LEN = 1010;
int n, vis[LEN];
vector<int> Map[LEN];

bool dfs(int vex, int col)
{
    vis[vex] = col;
    for(int i=0; i<Map[vex].size(); i++){
        int nv = Map[vex][i];
        if(!vis[nv]){if(!dfs(nv, -col))return false;}
        else if(vis[nv]==col)return false;
    }
    return true;
}

int main()
{
//    freopen("in.txt", "r", stdin);

    int a, b;
    while(scanf("%d", &n)!=EOF && n){
        for(int i=0; i<LEN; i++)Map[i].clear();
        while(scanf("%d%d", &a, &b)!=EOF){
            if(!a && !b)break;
            Map[a].PB(b);Map[b].PB(a);
        }
        memset(vis, 0, sizeof vis);
        bool ans = true;
        for(int i=1; i<=n; i++)
            if(vis[i]==0)if(!dfs(i, 1))ans = false;
        if(ans) printf("YES
");
        else printf("NO
");
    }
    return 0;
}