HihoCoder1181欧拉路(Fleury算法求欧拉路径)
2024-08-31 09:49:27
描述
在上一回中小Hi和小Ho控制着主角收集了分散在各个木桥上的道具,这些道具其实是一块一块骨牌。
主角继续往前走,面前出现了一座石桥,石桥的尽头有一道火焰墙,似乎无法通过。
小Hi注意到在桥头有一张小纸片,于是控制主角捡起了这张纸片,只见上面写着:
将M块骨牌首尾相连放置于石桥的凹糟中,即可关闭火焰墙。切记骨牌需要数字相同才能连接。
——By 无名的冒险者
小Hi和小Ho打开了主角的道具栏,发现主角恰好拥有M快骨牌。
小Ho:也就是说要把所有骨牌都放在凹槽中才能关闭火焰墙,数字相同是什么意思?
小Hi:你看,每一块骨牌两端各有一个数字,大概是只有当数字相同时才可以相连放置,比如:
小Ho:原来如此,那么我们先看看能不能把所有的骨牌连接起来吧。
输入
第1行:2个正整数,N,M。分别表示骨牌上出现的最大数字和骨牌数量。1≤N≤1,000,1≤M≤5,000
第2..M+1行:每行2个整数,u,v。第i+1行表示第i块骨牌两端的数字(u,v),1≤u,v≤N
输出
第1行:m+1个数字,表示骨牌首尾相连后的数字
比如骨牌连接的状态为(1,5)(5,3)(3,2)(2,4)(4,3),则输出"1 5 3 2 4 3"
你可以输出任意一组合法的解。
样例输入
5 5
3 5
3 2
4 2
3 4
5 1
样例输出
1 5 3 4 2 3
个人感觉原理就是充分利用搜索,或者栈,或者回溯的性质。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
int du[],used[],path[],n,m,cnt,tot=;
int Laxt[],Next[],To[];
void add(int u,int v)
{
Next[++tot]=Laxt[u];
Laxt[u]=tot;
To[tot]=v;
}
void dfs(int u)
{
for(int i=Laxt[u];i;i=Next[i]){
if(!used[i/]){
used[i/]=;
dfs(To[i]);
}
}
path[++cnt]=u;
}
int main()
{
int i,u,v;
scanf("%d%d",&n,&m);
for(i=;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
du[u]++;du[v]++;
}
int S=;
for(i=;i<=n;i++){
if(du[i]&) S=i;
}
dfs(S);
for(i=;i<=cnt;i++) printf("%d ",path[i]);
return ;
}
最新文章
- src/main/Java路径下的properties文件丢失
- 云计算CTO工作的具体内容(挺详细)
- java多线程详解(7)-线程池的使用
- Android中过场动画
- ArrayList Vector LinkedList 区别与用法
- Knockout.Js官网学习(系列)
- 查看Eclipse32位还是64位以及Eclipse的编译版本号,查看JDK是32位还是64位
- useful-scripts
- ARCI--做事情的重要方法论
- ACM1228_STL的应用
- SqlServer varchar数据中类似于1.1.1.1这种值的排序方法
- Suffix Automaton
- java生成二维码以及读取案例
- pachi 学习
- js跨域调用mvc ActionResult扩展
- JSONP跨域和CORS跨域
- 眠眠interview Question
- 运用jQuery实现动态点赞
- java反射子之获取方法信息(二)
- Javascript 链式作用域 function fn(){}和var fn=function(){}区别