题目翻译
一张无向图。
，由 $5$ 个点 $8$ 条边组成。请问如何才能从点 $1$ 出发不遗漏不重复走完所有边。
题目思路
简单的一笔画问题。通过一笔画我们不难想到七桥问题，作为尝试，我们都知道一张图内拥有 $0$ 或 $2$ 个奇点时才可被一笔画。
显然这张图上，奇点是 $1$ 和 $2$。因为题目说了从 $1$ 开始，所以起点为 $1$。
我们考虑对这张图进行搜索，枚举之后每一步走哪一条边，打上边是否走过的标记即可。
完整代码
这题没有输入，可直接打表。具体的答案在程序最后的注释。
代码
#include<bits/stdc++.h>
using namespace std;
bool vis[10][10];
int fa[10][10];
int ans[10];
void dfs(int u,int dep)
{
if(dep>8)
{
for(int i=1;i<=9;i++)
{
cout<<ans[i];
}
cout<<endl;
return;
}
for(int i=1;i<=5;i++)
{
if(fa[u][i]&&!vis[u][i])
{
ans[dep+1]=i;
vis[u][i]=vis[i][u]=1;
dfs(i,dep+1);
vis[u][i]=vis[i][u]=0;
}
}
}
int main()
{
fa[1][2]=1;fa[1][3]=2;fa[1][5]=3;
fa[2][1]=4;fa[2][3]=5;fa[2][5]=6;
fa[3][1]=7;fa[3][2]=8;fa[3][4]=9;fa[3][5]=10;
fa[4][3]=11;fa[4][5]=12;
fa[5][1]=13;fa[5][2]=14;fa[5][3]=15;fa[5][4]=16;
ans[1]=1;
dfs(1,1);
return 0;
}
/*
123153452
123154352
123451352
123453152
123513452
123543152
125134532
125135432
125315432
125345132
125431532
125435132
132153452
132154352
132534512
132543512
134512352
134512532
134521532
134523512
134532152
134532512
135123452
135125432
135215432
135234512
135432152
135432512
152134532
152135432
152345312
152354312
153123452
153125432
153213452
153254312
153452132
153452312
154312352
154312532
154321352
154325312
154352132
154352312
*/