题目大意:给出一个简单无向图，每个点的度为3。判断能否将此图分解成若干爪的形式，，使得每条边都只出现在唯一的爪中。（点可以多次出现在爪中）
这道题实质上就是问这个图是否为二分图，dfs判定即可
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string>#include<map> #include<set>#define eps 1e-6 #define LL long long using namespace std; const int maxn = 300 + 5;const int INF = 0x3f3f3f3f;vector<int> G[maxn]; //dfs给二分图进行黑白二着色,用颜色1表示黑色，颜色2表示白色，0表示没着色 int color[maxn]; //判断节点u所在的连通分量是否为二分图int n; bool bipartite(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(!bipartite(v)) return false;}}return true;} void init() {memset(color, 0, sizeof(color));for(int i = 1; i <= n; i++) G[i].clear();int x, y;while(scanf("%d%d", &x, &y) == 2 && x) {G[x].push_back(y);G[y].push_back(x);}}void solve() {color[1] = 1;if(bipartite(1)) puts("YES");else puts("NO");}int main() { //freopen("input.txt", "r", stdin);while(scanf("%d", &n) == 1 && n) {init();solve();}return 0;}
一定要记得挺身而出，即便帮不了忙，安慰也是最大的支持.
