资深光能
RT
资深守护
#include<iostream>
#include<cstring>
using namespace std;
int n,m;
int G[110][110];
int degree[110];
void dfs(int i){
for (int j=1;j<=n;j++){
if(G[i][j]){
G[i][j]=0;
G[j][i]=0;
dfs(j);
}
}
cout<<i<<" ";
}
int main(){
memset(degree,0,sizeof(degree));
cin>>n>>m;
for (int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
G[a][b]=1;
G[b][a]=1;
degree[a]++;
degree[b]++;
}
int start=1;
for (int i=1;i<=n;i++){
if (degree[i]%2!=0)
{
start=i;
break;
}
}
dfs(start);
return 0;
}欧拉路
资深光能
??
高级天翼
别抄了@黄昊轩
资深天翼
你这是刷分行为，老师以前讲过了！！！
初级光能
若图G中存在这样一条路径，使得它恰通过G中每条边一次,则称该路径为欧拉路径。若该路径是一个圈，则称为欧拉(Euler)回路。
具有欧拉回路的图称为欧拉图(简称E图)。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。
缔造者之神
1
新手守护
欧拉回路的作用:
在一张有向或无向图中求出一笔画问题的具体画法。
模板题：http://uoj.ac/problem/117
算法：
首先我们考虑如何判定这个图是否为欧拉回路
这时候我们对于有向图和无向图有不同的判定方法。
对于有向图，保证每个点的入度等于出度。
对于无向图，保证每个点的度数为偶数。
通常我们判断图是否联通，是在求欧拉回路（见下文）的过程中记录用到的边的数量，看是否与给定的边相等，若相等则联通。
因为如果通过深搜判断点的数量，可能题意描述点有n个，实际上一些点为单点，欧拉回路求的是道路，单点不影响。会出现误判。
然后我满考虑如何求出确切的欧拉回路。
我们可以用一个dfs来解决问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
void yxdfs(int x,int beg)
{
int ytp = head[x];
head[x] = nxt[ytp];
outd[x]--;
ind[to[ytp]]--;
jlb++;
if (to[ytp] != beg)
yxdfs(to[ytp],beg);
dl.push_back(ytp);
if (head[x])
yxdfs(x,x);
}
这是有向图的dfs，我们来分析一下。
参数x，表示当前搜到的点，beg表示这次搜索的起点。
我们删掉当前点的第一条边，如果删掉的这条边的指向不为搜索起点，那我们就不改变起点继续想下搜。并且搜回来记录我走的是那条边。如果说发现这条边还可以走出其他边，显然我们可以理解为从已经搜出的一张一笔画上，再从这点出发，再添加上一个一笔画，就像我们开始搜出了一条直线，后来在回溯的过程中，我们发现，有一个还有多余的边，那么从这点继续进行一笔画，并将其加入答案数组中，构成完整的一笔画。
同理无向图的dfs，删边稍微麻烦了一些，需要删除反向边，其余都一样。
最后我们获得了一个答案数组，我们应该如何将这个数组输出。
我们先考虑有向图，我们最早搜的点，是最后放入答案数组的，如果我们反向输出答案数组，那么显然边的指向是反的。所以我们要正想输出答案数组。
我们再考虑无向图。显然无论正反输出，对于边没有影响，虽然如此，我们的输出仍应该与样例保持一致，增加程序鲁棒性。
AC代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n,m,t,tp1,tp2,sum,js,jlb;
int head[200000],nxt[500000],to[500000],ind[200000];
int tod[200000],fx[500000],outd[200000];
bool vis[20000];
vector <int> dl;
void cr(int x,int y)
{
sum++;
nxt[sum] = head[x];
head[x] = sum;
to[sum] = y;
}
bool pd1()
{
for (int i = 1; i <= n; i++)
{
if (ind[i] & 1) return false;
}
return true;
}
void del(int x,int y)
{
if (to[head[x]] == y)
{
head[x] = nxt[head[x]];
return;
}
for (int i = head[x]; i; i = nxt[i])
{
if (to[nxt[i]] == y)
{
nxt[i] = nxt[nxt[i]];
return;
}
}
}
void wxdfs(int x,int beg)
{
int wtp = head[x];
head[x] = nxt[wtp];
del(to[wtp],x);
ind[x]--;
jlb++;
ind[to[wtp]]--;
if (to[wtp] != beg && to[wtp])
wxdfs(to[wtp],beg);
if (wtp) dl.push_back(wtp);
if (head[x]) wxdfs(x,x);
}
void work1()
{
for (int i = 1; i <= n; i++)
{
if (ind[i])
{
wxdfs(i,i);
break;
}
}
}
void print1()
{
for (int i = 0; i < dl.size(); i++)
{
int tan = 0;
tan = (dl[i] + 1) / 2;
if (dl[i] & 1) tan *= -1;
printf("%d ",tan);
}
}
void read1()
{
scanf("%d%d",&n,&m);
for (int i = 1; i <= m; i++)
{
scanf("%d%d",&tp1,&tp2);
cr(tp1,tp2);
cr(tp2,tp1);
ind[tp1]++;
ind[tp2]++;
}
if (!pd1())
{
printf("NO\n");
return;
}
else
{
work1();
if (jlb < m) printf("NO\n");else
{
printf("YES\n");
print1();
}
}
}
bool pd2()
{
for (int i = 1;i <= n;i++)
{
if (ind[i] != outd[i]) return false;
}
return true;
}
void print2()
{
for (int i = dl.size() - 1;i >= 0;i--)
printf("%d ",dl[i]);
}
void yxdfs(int x,int beg)
{
int ytp = head[x];
head[x] = nxt[ytp];
outd[x]--;
ind[to[ytp]]--;
jlb++;
if (to[ytp] != beg)
yxdfs(to[ytp],beg);
dl.push_back(ytp);
if (head[x])
yxdfs(x,x);
}
void work2()
{
for (int i = 1;i <= n;i++)
{
if (outd[i])
{
yxdfs(i,i);
break;
}
}
}
void read2()
{
scanf("%d%d",&n,&m);
for (int i = 1;i <= m;i++)
{
scanf("%d%d",&tp1,&tp2);
cr(tp1,tp2);
ind[tp2]++;
outd[tp1]++;
}
if (!pd2())
{
printf("NO\n");
}else
{
work2();
if (jlb < m)
{
printf("NO\n");
return;
}else
{
printf("YES\n");
print2();
}
}
}
void sread()
{
scanf("%d",&t);
if (t == 1) read1();
else
read2();
}
int main()
{
sread();
return 0;
}
