uva 10054 The Necklace 拼项链 欧拉回路基础应用
昨天做了道水题，今天这题是比较水的应用。
给出n个项链的珠子，珠子的两端有两种颜色，项链上相邻的珠子要颜色匹配，判断能不能拼凑成一天项链。
是挺水的，但是一开始我把整个项链看成一个点，然后用dfs去找，结果超时了。
后来瞄了一眼题解发现把颜色当成点，一个珠子就是一条路，这样就能得到一个无向图了，然后判断欧拉回路即可。
这题默认是珠子为连通的，所以不需要判断连通性。然后判断节点的度数是否为偶数，也就是是否为欧拉回路，如果是的话用深搜输出珠子的顺序。深搜时输出记得得放在递归之后，用逆序输出，不然会出错的，具体看Titanium大神的博客，他介绍的很清楚。（Orz）
代码：
#include <cstdio>
#include <cstring>
const int maxn = 51;
int t, n;
int id[maxn], g[maxn][maxn];
void euler(int u) {
for (int i = 1; i <= 50; i++)
if (g[u][i]) {
g[u][i]--;
g[i][u]--;
euler(i);
printf("%d %d\n", i, u);
}
}
int main() {
scanf("%d", &t);
int a, b;
for (int cas = 1; cas <= t; cas++) {
scanf("%d", &n);
memset(id, 0, sizeof(id));
memset(g, 0, sizeof(g));
for (int i = 0; i < n; i++) {
scanf("%d%d", &a, &b);
g[a][b]++;
g[b][a]++;
id[a]++;
id[b]++;
}
int i;
for (i = 1; i <= 50; i++)
if (id[i] % 2)
break;
if (cas > 1)
printf("\n");
printf("Case #%d\n", cas);
if (i <= 50)
printf("some beads may be lost\n");
else
for (i = 0; i <= 50; i++)
euler(i);
}//for
return 0;
}
#include <cstdio>
#include <cstring>
const int maxn = 51;
int t, n;
int id[maxn], g[maxn][maxn];
void euler(int u) {
for (int i = 1; i <= 50; i++)
if (g[u][i]) {
g[u][i]--;
g[i][u]--;
euler(i);
printf("%d %d\n", i, u);
}
}
int main() {
scanf("%d", &t);
int a, b;
for (int cas = 1; cas <= t; cas++) {
scanf("%d", &n);
memset(id, 0, sizeof(id));
memset(g, 0, sizeof(g));
for (int i = 0; i < n; i++) {
scanf("%d%d", &a, &b);
g[a][b]++;
g[b][a]++;
id[a]++;
id[b]++;
}
int i;
for (i = 1; i <= 50; i++)
if (id[i] % 2)
break;
if (cas > 1)
printf("\n");
printf("Case #%d\n", cas);
if (i <= 50)
printf("some beads may be lost\n");
else
for (i = 0; i <= 50; i++)
euler(i);
}//for
return 0;
}
补充：软件开发 , C++ ,
