The Necklace
My little sister had a beautiful necklace made of colorful beads. Two successive beads in the necklace shared a common color at their meeting point. The figure below shows a segment of the necklace:
But, alas! One day, the necklace was torn and the beads were all scattered over the floor. My sister did her best to recollect all the beads from the floor, but she is not sure whether she was able to collect all of them. Now, she has come to me for help. She wants to know whether it is possible to make a necklace using all the beads she has in the same way her original necklace was made and if so in which order the bids must be put. Please help me write a program to solve the problem.
Input
The input contains T test cases. The first line of the input contains the integer T. The first line of each test case contains an integer N (5 ≤ N ≤ 1000) giving the number of beads my sister was able to collect. Each of the next N lines contains two integers describing the colors of a bead. Colors are represented by integers ranging from 1 to 50.
Output
For each test case in the input first output the test case number as shown in the sample output. Then if you apprehend that some beads may be lost just print the sentence “some beads may be lost” on a line by itself. Otherwise, print N lines with a single bead description on each line. Each bead description consists of two integers giving the colors of its two ends. For 1 ≤ i ≤ N1, the second integer on line i must be the same as the first integer on line i + 1. Additionally, the second integer on line N must be equal to the first integer on line 1. Since there are many solutions, any one of them is acceptable. Print a blank line between two successive test cases.
Sample Input
2
5
1 2
2 3
3 4
4 5
5 6
5
2 1
2 2
3 4
3 1
2 4Sample Output
Case #1 some beads may be lost
Case #2
2 1
1 3
3 4
4 2链接
https://cn.vjudge.net/problem/UVA-10054
题意
无向图求欧拉回路。
题解
首先判断一下每个点的度数是否都是偶数，如果出现奇数那就不会形成环。然后直接使用dfs或者Fleury算法求欧拉回路。
注意：如果本题判断整个图是否连通的话，会有问题，因为可能一个单独的连通分量构成一个欧拉回路，比如下面这组数据，来自uDebug。
Input
1
4
1 2
2 1
3 4
4 3
Output
Case #1
1 2
2 1代码
- 直接BFS
| Status | Accepted |
|---|---|
| Time | 130ms |
| Length | 1322 |
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 60;
int G[maxn][maxn];
int degree[maxn];
int n, m;
void init()
{
memset(G, 0, sizeof(G));
memset(degree, 0, sizeof(degree));
}
void Euler(int u)
{
for (int i = 1; i <= n; ++i)
{
if (G[u][i] > 0)
{
G[u][i]--;
G[i][u]--;
Euler(i); // 先dfs完，最后再进行逆序输出，不然可能会出现(1, 2)、(1, 3)
printf("%d %d\n", i, u);
}
}
}
int main()
{
int u, v, T, s, kase = 0;
scanf("%d", &T);
while (T--)
{
bool flag = true;
scanf("%d", &m);
init();
n = 0;
for (int i = 0; i < m; ++i)
{
scanf("%d%d", &u, &v);
G[u][v]++; // 无向图可能存在重边
G[v][u]++;
degree[u]++;
degree[v]++;
n = max(n, max(u, v));
s = u;
}
for (int i = 1; i <= n; ++i)
{
if ((degree[i] & 1)) // 欧拉回路要求所有点的度数均为偶数，出现度数为奇数
flag = false;
}
printf("Case #%d\n", ++kase);
if (!flag)
printf("some beads may be lost\n");
else
Euler(s);
if (T > 0)
printf("\n");
}
return 0;
}- 使用Fleury算法
| Status | Accepted |
|---|---|
| Time | 126ms |
| Length | 2126 |
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 60;
vector <int> V;
int G[maxn][maxn];
int degree[maxn];
int ans[maxn*maxn]; // ans栈数组开小了玄学TLE
int n, m, top;
void init()
{
memset(G, 0, sizeof(G));
memset(degree, 0, sizeof(degree));
memset(ans, 0, sizeof(ans));
V.clear(); // V忘记初始化OLE玄学
}
void dfs(int u) // 寻找一条路径
{
ans[++top] = u;
for (int i = 1; i <= n; ++i)
{
if (G[u][i] > 0) // “删边”
{
G[u][i]--;
G[i][u]--;
dfs(i);
break; // 一条边
}
}
}
void fleury(int u)
{
top = 1;
ans[top] = u;
while (top > 0)
{
int k = 0;
for (int i = 1; i <= n; ++i) // 判断是否可扩展
{
if (G[ans[top]][i] > 0) // 若存在一条从ans[top]出发的边 那么就可以扩展一条“回路”
{
k = 1;
break;
}
}
if (k == 0) // 没有其他的边了，不可扩展，保存结果
V.push_back(ans[top--]);
else if (k == 1) // 对可扩展的路径进行dfs
dfs(ans[top--]);
}
}
int main()
{
//freopen("/Users/taifu/Codes/CPP/data.in", "r", stdin);
//freopen("/Users/taifu/Codes/CPP/data.out","w",stdout);
int u, v, T, s, kase = 0;
scanf("%d", &T);
while (T--)
{
bool flag = true;
scanf("%d", &m);
init();
n = 0;
for (int i = 0; i < m; ++i)
{
scanf("%d%d", &u, &v);
G[u][v]++; // 无向图可能存在重边
G[v][u]++;
degree[u]++;
degree[v]++;
n = max(n, max(u, v));
}
s = u;
for (int i = 1; i <= n; ++i)
{
if ((degree[i] & 1))
flag = false;
}
if (!flag)
printf("Case #%d\nsome beads may be lost\n", ++kase);
else
{
fleury(s);
printf("Case #%d\n", ++kase);
printf("%d %d\n", V[0], V[1]);
for (int i = 2; i < V.size(); ++i)
printf("%d %d\n", V[i-1], V[i]);
}
if (T > 0)
printf("\n");
}
return 0;
}- 附上判连通图的代码（WA）
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 60;
vector <int> V;
int G[maxn][maxn];
int degree[maxn];
int ans[maxn*maxn];
bool vis[maxn];
int n, m, top, cnt1, cnt2;
void init()
{
cnt1 = cnt2 = 0;
memset(vis, 0, sizeof(vis));
memset(G, 0, sizeof(G));
memset(degree, 0, sizeof(degree));
memset(ans, 0, sizeof(ans));
V.clear();
}
void con_dfs(int u)
{
vis[u] = true;
cnt2++;
for (int i = 1; i <= n; ++i)
{
if (G[u][i] > 0 && !vis[i])
con_dfs(i);
}
}
void dfs(int u) // 寻找一条路径
{
ans[++top] = u;
for (int i = 1; i <= n; ++i)
{
if (G[u][i] > 0) // “删边”
{
G[u][i]--;
G[i][u]--;
dfs(i);
break; // 一条边
}
}
}
void fleury(int u)
{
top = 1;
ans[top] = u;
while (top > 0)
{
int k = 0;
for (int i = 1; i <= n; ++i) // 判断是否可扩展
{
if (G[ans[top]][i] > 0) // 若存在一条从ans[top]出发的边 那么就可以扩展一条“回路”
{
k = 1;
break;
}
}
if (k == 0) // 没有其他的边了，不可扩展，保存结果
V.push_back(ans[top--]);
else if (k == 1) // 对可扩展的路径进行dfs
dfs(ans[top--]);
}
}
int main()
{
//freopen("/Users/taifu/Codes/CPP/data.in", "r", stdin);
//freopen("/Users/taifu/Codes/CPP/data.out","w",stdout);
int u, v, T, s, kase = 0;
scanf("%d", &T);
while (T--)
{
bool flag = true;
scanf("%d", &m);
init();
n = 0;
for (int i = 0; i < m; ++i)
{
scanf("%d%d", &u, &v);
G[u][v]++; // 无向图可能存在重边
G[v][u]++;
degree[u]++;
degree[v]++;
n = max(n, max(u, v));
if (!vis[u])
{
cnt1++;
vis[u] = true;
}
if (!vis[v])
{
cnt1++;
vis[v] = true;
}
}
s = u;
memset(vis, 0, sizeof(vis));
con_dfs(s);
if (cnt1 != cnt2) // 判断是否连通
flag = false;
for (int i = 1; i <= n; ++i)
{
if ((degree[i] & 1))
flag = false;
}
if (!flag)
printf("Case #%d\nsome beads may be lost\n", ++kase);
else
{
fleury(s);
printf("Case #%d\n", ++kase);
printf("%d %d\n", V[0], V[1]);
for (int i = 2; i < V.size(); ++i)
printf("%d %d\n", V[i-1], V[i]);
}
if (T > 0)
printf("\n");
}
return 0;
}栈数组开小了导致TLE，玄学？保存结果的vector忘记初始化，OLE错误，判连通图WA。关于直接dfs和使用Fleury算法求欧拉路...
关于逆序输出建议阅读这篇博客。
The end.
2018-07-26 星期四