有一种由彩色的珠子连接成的项链。每个珠子的两半有两个不同的颜色，相邻的珠子的接触的地方颜色相同。现在有一些零碎的珠子，问是否可以还原成一个项链。颜色用1~50来表示。如果不能，输出“some beads may be lost”，如果能，输出项链的路径。

实际上就是给定一无向图（因为对于珠子[1, 2]，可以倒过来就是[2, 1]，所以是无向图），判断能否形成欧拉回路，若能形成，输出欧拉回路。

若每个顶点的度都是偶数，则能形成欧拉回路，否则不能形成欧拉回路。判断后用 dfs 来输出回路就好了。

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int G[N][N];
int cnt[N], vis[N];
void dfs(int x)
{
  for (int i = 0; i < N; i++) {
    if (G[x][i]) {
      G[x][i]--;
      G[i][x]--;
      dfs(i);
      printf("%d %d\n", i, x);
    }
  }
}
int main()
{
  int t, cas = 1;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    memset(G, 0, sizeof(G));
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; i++) {
      int u, v;
      scanf("%d %d", &u, &v);
      G[u][v]++;
      G[v][u]++;
      cnt[u]++;
      cnt[v]++;
    }
    printf("Case #%d\n", cas++);
    int ok = 1;
    for (int i = 1; i < N; i++) {
      if (cnt[i] & 1) {
        ok = 0;
        break;
      }
    }
    if (!ok) {
      puts("some beads may be lost");
    } else {
      memset(vis, 0, sizeof(vis));
      for (int i = 1; i < N; i++) {
        dfs(i);
      }
    }
    if (t) {
      puts("");
    }
  }
  return 0;
}

去打赏