周口网站建设哪家好,wordpress证优客,福田公司在哪里,自学编程入门先学什么1 /*2 题意#xff1a;打印欧拉回路#xff01;3 思路#xff1a;开始时不明白#xff0c;dfs为什么是后序遍历#xff1f; 4 因为欧拉回路本身是一条回路#xff0c;那么我们在dfs时#xff0c;可能存在提前找到回路#xff0c;这条回路可能不是欧拉回路打印欧拉回路3 思路开始时不明白dfs为什么是后序遍历 4 因为欧拉回路本身是一条回路那么我们在dfs时可能存在提前找到回路这条回路可能不是欧拉回路5 因为没有遍历完成所有的边如果写成前序遍历的话存储起来的路径就不是一条完整的路径了它有可能6 是多条回路组成的答案就是错误 的如果是后序遍历的话当dfs是遇到了回路那么就退出当前栈的搜索7 去寻找其他的路径最终得到的只有一条回路路径--欧拉回路~ 8 */ 9 #includeiostream
10 #includecstring
11 #define M 55
12 #define Max 0x3f3f3f3f
13 using namespace std;
14
15 int cnt[M][M];
16 int deg[M];
17 int map[M][M];
18 int x;
19
20 struct Point{
21 int x, y;
22 Point(){}
23
24 Point(int x, int y){
25 this-xx;
26 this-yy;
27 }
28 };
29
30 Point p[1005];
31 int top;
32
33 void dfs(int u){
34 if(!deg[u]) return;
35 for(int i1; i50; i)
36 if(map[u][i] cnt[u][i]){
37 --cnt[u][i];
38 --cnt[i][u];
39 --deg[u];
40 --deg[i];
41 dfs(i);
42 p[top]Point(u, i);
43 }
44 }
45
46 int main(){
47 int t, n, k0;
48 cint;
49 while(t--){
50 cinn;
51 xMax;
52 memset(cnt, 0, sizeof(cnt));
53 memset(map, 0, sizeof(map));
54 memset(deg, 0, sizeof(deg));
55 for(int i1; in; i){
56 int u, v;
57 cinuv;
58 deg[u];
59 deg[v];
60 map[u][v]1;
61 map[v][u]1;
62 cnt[u][v];
63 cnt[v][u];
64 if(xu) xu;
65 if(xv) xv;
66 }
67 int ok0;
68 for(int i1; i50; i)
69 if(deg[i]%2!0){
70 ok1;
71 break;
72 }
73 coutCase #kendl;
74 if(ok){
75 coutsome beads may be lostendl;
76 if(t) coutendl;
77 continue;
78 }
79 top0;
80 dfs(x);
81 if(topn){
82 for(top; top1; --top)
83 coutp[top].x p[top].yendl;
84 }
85 else coutsome beads may be lostendl;
86 if(t) coutendl;
87 }
88 return 0;
89 } 转载于:https://www.cnblogs.com/hujunzheng/p/3895454.html
