题意：这道题主要是定义了一个交叫爪子的图：
然后他会给你一个每个结点度数都是三的无向图。问你能否能否拆成爪子图。（就是分成若干个子图，原图中的每条边都只能在一张子图中出现一次，点可以重复出现）。
思路：这道题我们可以画几个推理一下，会发现一个结论当且仅当图是而分图的时候是可以的，然后剩下来的就是染色判定了。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstring> 6 #include <algorithm> 7 #include <queue> 8 #include <stack> 9 #include <vector> 10 #define MP(a, b) make_pair(a, b) 11 #define PB(a) push_back(a) 12 13 using namespace std; 14 15 typedef long long ll; 16 typedef pair<int ,int> pii; 17 typedef pair<unsigned int, unsigned int> puu; 18 typedef pair<int ,double> pid; 19 typedef pair<ll, int> pli; 20 21 const int INF = 0x3f3f3f3f; 22 const double eps = 1e-6; 23 const int LEN = 1010; 24 int n, vis[LEN]; 25 vector<int> Map[LEN]; 26 27 bool dfs(int vex, int col) 28 { 29 vis[vex] = col; 30 for(int i=0; i<Map[vex].size(); i++){ 31 int nv = Map[vex][i]; 32 if(!vis[nv]){if(!dfs(nv, -col))return false;} 33 else if(vis[nv]==col)return false; 34 } 35 return true; 36 } 37 38 int main() 39 { 40 // freopen("in.txt", "r", stdin); 41 42 int a, b; 43 while(scanf("%d", &n)!=EOF && n){ 44 for(int i=0; i<LEN; i++)Map[i].clear(); 45 while(scanf("%d%d", &a, &b)!=EOF){ 46 if(!a && !b)break; 47 Map[a].PB(b);Map[b].PB(a); 48 } 49 memset(vis, 0, sizeof vis); 50 bool ans = true; 51 for(int i=1; i<=n; i++) 52 if(vis[i]==0)if(!dfs(i, 1))ans = false; 53 if(ans) printf("YES\n"); 54 else printf("NO\n"); 55 } 56 return 0; 57 }