骑马修栅栏（dfs）

#include<bits/stdc++.h>

using namespace std;

const int N = 1e3 + 26;

int mapp[N][N], S[N], ans[N];

int n, res;

void dfs(int i)

{

for (int j = 1; j <= n; j++)

{

if (mapp[i][j])

{

mapp[i][j]--; mapp[j][i]--;

dfs(j);

}

}

ans[res++] = i;

}

int main()

{

int m;

cin >> m;

for (int i = 1; i <= m; i++)

{

int a, b;

cin >> a >> b;

mapp[a][b]++; mapp[b][a]++;//记录路径

S[a]++;

S[b]++;

n = max(n, max(a, b));//找到最大点

}

int s = 1;

for (int i = 1; i <= n; i++)

{

if (S[i] & 1)

{

s = i;//找到起始点

break;

}

}

dfs(s);

for (int i = res - 1; i >= 0; i--)

{

cout << ans[i] << endl;

}

}

//欧拉路径/欧拉回路的题目几步走

//1.记录路径和出度入度

//2.欧拉路径就找起始点，欧拉回路起始点就是1

//3.dfs开始沿着起始点走利用数组存走过的路径，由于是倒叙记录的所以最后要从后往前输出