题目链接
题意：能否将一张无向连通图分解成多个爪型。每一条边仅仅能属于一个爪型，每一个点的度数为3.
思路：当图分解成类干个爪型时，每条边仅仅属于一个爪子，所以每条边的两个点一定要处于2个不同的鸡爪中
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>using namespace std;const int MAXN = 305;vector<int> g[MAXN];
int n, color[MAXN];void init() {for (int i = 0; i < n; i++) g[i].clear();
}bool bipartite(int u) {for (int i = 0; i < g[u].size(); i++) {int v = g[u][i]; if (color[u] == color[v]) return false; if (!color[v]) {color[v] = 3 - color[u];if (!bipartite(v)) return false;}}return true;
}int main() {while (scanf("%d", &n) && n) {init();int u, v; while (scanf("%d%d", &u, &v)) {if (u == 0 && v == 0)break;u--;v--;g[u].push_back(v);g[v].push_back(u);}memset(color, 0, sizeof(color));color[0] = 1; if(bipartite(0)) printf("YES\n"); else printf("NO\n"); } return 0;
}