呼~~终于把它A掉了
这道题是判断是否存在欧拉回路的,把颜色看成点,珍珠看成边,然后统计每一个点的度,如果有奇度就表明欧拉回路不存在,如果存在的话直接dfs出欧拉回路,然后扔到栈里最后直接输出就行了。(仰慕佳哥)
#include <cstdio> #include <cstring> #include <algorithm> #include <stack> #include <iostream> using namespace std; const int N = 55; int g[N][N], dg[N]; stack<pair<int, int> >st; int is_euler(int mn){ int s = -1; for (int i = 1; i <= mn; i++){ if (dg[i]){ if (s == -1) s = i; if (dg[i] % 2) return -1; } } return s; } void dfs(int cur, int mn){ for (int i = 1; i <= mn; i++){ if (g[cur][i]){ g[cur][i] -= 1; g[i][cur] -= 1; dfs(i, mn); st.push(make_pair(cur, i)); } } } int main(){ //freopen("out.txt", "w", stdout); int cs, n; scanf("%d", &cs); for (int p = 1; p <= cs; p++){ memset(g, 0, sizeof(g)); memset(dg, 0, sizeof(dg)); if (p > 1) printf("\n"); scanf("%d", &n); int x, y, mn = 0; for (int i = 0; i < n; i++){ scanf("%d%d", &x, &y); g[x][y] += 1; g[y][x] += 1; dg[x] += 1; dg[y] += 1; mn = max(mn, max(x, y)); } int f = is_euler(mn); printf("Case #%d\n", p); if (f == -1){ puts("some beads may be lost"); } else{ dfs(f, mn); while(!st.empty()){ printf("%d %d\n", st.top().first, st.top().second); st.pop(); } } } return 0; }