hihoCoder week 50-1-欧拉路·二
题目1 : 欧拉路·二
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在上一回中小Hi和小Ho控制着主角收集了分散在各个木桥上的道具，这些道具其实是一块一块骨牌。
主角继续往前走，面前出现了一座石桥，石桥的尽头有一道火焰墙，似乎无法通过。
小Hi注意到在桥头有一张小纸片，于是控制主角捡起了这张纸片，只见上面写着：
将M块骨牌首尾相连放置于石桥的凹糟中，即可关闭火焰墙。切记骨牌需要数字相同才能连接。
——By 无名的冒险者
小Hi和小Ho打开了主角的道具栏，发现主角恰好拥有M快骨牌。
小Ho：也就是说要把所有骨牌都放在凹槽中才能关闭火焰墙，数字相同是什么意思？
小Hi：你看，每一块骨牌两端各有一个数字，大概是只有当数字相同时才可以相连放置，比如：
小Ho：原来如此，那么我们先看看能不能把所有的骨牌连接起来吧。
提示：Fleury算法求欧拉路径
输入
第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
上一周学习了怎样判断欧拉通路，这周要给出一条具体的欧拉通路。 欧拉通路的求解使用Fleury算法，其伪代码如下： [cpp] DFS(u): While (u存在未被删除的边e(u,v)) 删除边e(u,v) DFS(v) End PathSize ← PathSize + 1 Path[ PathSize ] ← u [/cpp] 非常简洁漂亮，本题完整代码如下： [cpp] #include<iostream> #include<cstdio> using namespace std; const int kMaxN = 1005,kMaxM=5005; int n, m,path_size=0; int path[kMaxM];//是kMaxM而非kMaxN int edge[kMaxN][kMaxN]; void dfs(int p) { for (int i = 1; i <= n; i++) { if (edge[p][i]>0) { edge[p][i]–; edge[i][p]–; dfs(i); } } path[path_size++] = p; } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &m); int u, v; for (int i = 0; i < m; i++) { scanf("%d %d", &u, &v); edge[u][v]++;//防止有重边 edge[v][u]++; } dfs(1); for (int i = 0; i < path_size; i++) printf("%d ", path[i]); return 0; } [/cpp] 本代码提交AC，用时15MS，内存3MB。需要提醒的是，path的实际大小是m+1，而非n；另外为了防止有重边出现，edge用于记录边的数量，而非是否有边存在。 AC之后我还尝试了先找出欧拉通路的起点，再从起点开始dfs的方法，这种方法并没有更快，因为不论是从哪个点开始dfs，每个点的for循环都要完整执行，所以时间并不会减少，反而会由于寻找起点而增加时间。]]>