题目大意：1～50代表颜色，俩个颜色一组，要求相连的组之间颜色相同，连成一条项链，并输出
解题思路：判断是否连通，然后判断是否是欧拉回路，最后逆序输出
#include <stdio.h> #include <iostream> #include <queue> #include <string.h> using namespace std; int all; int flag[100]; int cou[100]; int sum; int m; queue<int> que; int range[100][100]; int dfs(int a) { if(sum == all) return 1; for(int i = 1; i <= 50; i++) { if(range[a][i] && flag[i] == 0) { flag[i] = 1; sum++; if(sum == all) return 1; int b = dfs(i); if(b == 1) return 1; } } return 0; } void dfs2(int a) { for(int i = 1; i <= 50; i++) { if(range[a][i]) { range[a][i]--; range[i][a]--; dfs2(i); printf("%d %d\n", i, a); } } } int main() { int n; cin >> n; int x = 0; while(n--) { memset(flag, 0, sizeof(flag)); memset(cou, 0, sizeof(cou)); memset(range, 0, sizeof(range)); while(!que.empty()) que.pop(); all = 0; sum = 0; x++; cin >> m; int num1, num2; for(int i = 0; i < m; i++) { cin >> num1; cin >> num2; if(cou[num1] == 0) { que.push(num1); all++; } cou[num1]++; if(cou[num2] == 0) { que.push(num2); all++; } cou[num2]++; range[num1][num2]++; range[num2][num1]++; } int l = dfs(num1); int re = 0; if(l == 1) { while(!que.empty()) { int t = que.front(); if(cou[t] % 2 != 0) break; que.pop(); } if(que.empty()) re = 1; } printf("Case #%d\n", x); if(re == 0) printf("some beads may be lost\n"); else { sum = 0; dfs2(num1); } if(n != 0) printf("\n"); } return 0; }