题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=995
题目类型: 欧拉回路
题目:
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.
题目大意翻译:
我的妹妹有一串由各种颜色组成的项链。 项链中两个连续珠子的接头处共享同一个颜色。 如上图, 第一个珠子是green+red, 那么接这个珠子的必须以red开头,如图的red+white.
噢!天啊! 一天, 项链项链被扯断了,珠子掉落了一地。我的妹妹竭尽全力的把珠子一个个捡起来, 但是她不确定是否全部捡回来了。 现在,她叫我帮忙。
她想知道是否可能把这些珠子全部连接起来, 连接的方法和项链原来的方法一样。
请帮我写一个程序解决这个问题。
样例输入:
2
5
1 2
2 3
3 4
4 5
5 6
5
2 1
2 2
3 4
3 1
2 4
样例输出:
Case #1
some beads may be lost
Case #2
2 1
1 3
3 4
4 2
2 2
思路与总结:
这题就是欧拉回路+打印路径,
和UVa 10129 - Play on Words, 欧拉道路这题很像,
有所不同的是,那题是有向图,而这一题是无向图, 那一题是求欧拉道路,而这一题求的是欧拉回路。
欧拉道路和欧拉回路的区别是, 欧拉回路是要从某一点出发,最后又回到这一点,形成回路。而欧拉道路是从一点出发,到另一个点结束。
打印欧拉回路的方法, 刘汝佳《算法入门经典》P112上有详细介绍:
下面是的递归函数同时适用于欧拉道路和回路。如果需要打印的是欧拉道路,在主程序调用时,参数必须是道路的起点。另外,打印的顺序是你序的,因此真正使用这份
代码时,应当把printf语句替换成一条push语句,把边压入一个栈内。
void euler(int u){
for(int v=0; v<MAXN; ++v) if(G[u][v]){
vis[u][v] = vis[v][u] = 1;
euler(v);
printf("%d %d\n", u,v);
}
}
上代码使用于无向图, 如果改成有向图,把vis[u][v] = vis[v][u] = 1改成vis[u][v]= 1即可。
在这一题中, 由于可能会出现重复的,比如:
1 2
2 2
2 2
2 2
2 3
3 1
1 2
2 1
所以需要稍微改变一下
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<stack>
#define MAXN 60
using namespace std;
int vis[MAXN],cnt[MAXN],G[MAXN][MAXN],T, vis2[MAXN][MAXN], N, a, b;
struct Node {int u,v; };
stack<Node>st;
void dfs(int u){
vis[u] = true;
for(int i=0; i<MAXN; ++i){
if(G[u][i] && !vis[i])
dfs(i);
}
}
void euler(int u){
for(int v=0; v<MAXN; ++v) if(G[u][v]){
--G[u][v]; --G[v][u];
euler(v);
Node t;
t.u = u, t.v = v;
// st.push(t);
printf("%d %d\n", u,v);
}
}
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif
int cas=1;
scanf("%d",&T);
while(T--){
memset(G, 0, sizeof(G));
memset(cnt, 0, sizeof(cnt));
scanf("%d",&N);
for(int i=0; i<N; ++i){
scanf("%d %d",&a,&b);
++G[a][b];
++G[b][a];
++cnt[a];
++cnt[b];
}
bool flag=true;
for(int i=0; i<MAXN; ++i){
if(cnt[i] & 1){ flag=false; break;}
}
printf("Case #%d\n",cas++);
if(flag){
memset(vis, 0, sizeof(vis));
memset(vis2, 0, sizeof(vis2));
int flag2=true;
for(int i=0; i<MAXN; ++i)
if(cnt[i]) { dfs(i); break; }
for(int i=0; i<MAXN; ++i){
if(cnt[i] && !vis[i]) {flag2=false; break;}
}
if(flag2){
for(int i=0; i<MAXN; ++i) if(cnt[i]){
euler(i);
break;
}
// 这里可以递归时直接逆向打印,也可存到栈里在打印出来
// while(!st.empty()){
// printf("%d %d\n", st.top().u, st.top().v);
// st.pop();
// }
}
else printf("some beads may be lost\n");
}
else{
printf("some beads may be lost\n");
}
if(T) printf("\n");
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
这里以构建一个度全部相同的欧拉回路,并输出欧拉回路的路径 1.构建欧拉回路 连通主要是靠树来保证,首先建立一个度为k的完全图,其中会有很多需要主要的地方 (1)首先构造树 =>保证顶点连通 (2)将度的点...
欧拉回路C++程序 随机输入任意点数,给出图中存在的欧拉回路
Catenyms poj hoj 欧拉回路输出路径
图论——欧拉回路的Fleury算法 根据离散数学教材中思想 实现求欧拉回路。
图论- 图的遍历- 欧拉通路与欧拉回路问题.rar
欧拉回路性质与应用探究欧拉回路性质与应用探究欧拉回路性质与应用探究
COMSOL 两相流 欧拉-欧拉 双流体模型
Euler_difference.txt+前向欧拉法+后向欧拉法+中心差分法+matlab程序
算法-欧拉回路(HDU-1878)(包含源程序).rar
图论中有关求解欧拉路径和欧拉回路的基本方法,并有详细的示例说明。
欧拉回路,又称“一笔画”,是图论中可行遍性问题的一种。本文首先介绍了欧拉回路的相关理论知识,以及求欧拉回路的算法。然后通过几个实例,介绍了与欧拉回路相关的几类典型问题。最后对欧拉回路的模型进行了总结,...
关于算法与图论中有向图的欧拉回路的判断,判断一个有向图是否有欧拉回路
第八讲-机器人动力学--牛顿-欧拉方程.ppt
实现了欧拉回路的程序实现即遍历图输出欧拉回路
2022级图论-欧拉回路和最短路_题解
对欧拉回路的实验报告,有利于大家更好地理解欧拉回路,对要实验报告的人很适合。本算法使用c语言编写的 如需其他语言请自行更改。
找欧拉回路,本程序实现了对一个欧拉图形找其欧拉回路
自己用C写的无向图找欧拉回路的一个例子。主要用于数据结构的学习
实 验 报 告(2019 / 2020 学年 第 一 学期) 课程名称 离散数学 实验名称 图的生成及欧拉回路的确定 实验时间 2021 年 1