Caro23333 @ 2017-08-01 08:33:11
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 1005;
int a[MAXN][MAXN],d[MAXN];
int maxp = 0,minp = 1<<30;
int n;
int ans[MAXN];
void dfs(int x)
{
printf("%d\n",x);
for(int i = minp; i<=maxp; i++)
{
if(a[x][i])
{
a[x][i]--;
a[i][x]--;
dfs(i);
}
}
//ans[++n] = x;
}
int main()
{
int f;
cin >> f;
int x,y;
for(int i = 1; i<=f; i++)
{
scanf("%d%d",&x,&y);
a[x][y]++;
a[y][x]++;
d[x] += 1;
d[y] += 1;
maxp = max(maxp,max(x,y));
minp = min(minp,min(x,y));
}
int i;
for(i = minp; i<=maxp; i++)
{
if(d[i]%2)
{
dfs(i);
break;
}
}
if(i==maxp+1)
dfs(1);
// for(int j = n; j>=1; j--)
// printf("%d\n",ans[j]);
system("pause");
return 0;
}
我想问,dfs里面的部分为什么不能直接输出答案?改成将路径存到ans数组就AC了
by scarborough_fair @ 2017-08-01 10:30:54
dfs里的ans是在回退时存储的,编号当然是倒着打的
by Caro23333 @ 2017-08-01 11:16:17
@changyu2 但是直接输出也有74分啊
by WilliamPen @ 2017-10-01 20:54:17
因为如果搜到一个无法往下搜的点,一定是终点,会优先进队,如果其他还有什么环,会继续按顺序进队,你画个搜索树模拟一下试试
by WilliamPen @ 2017-10-01 20:54:51
然后楼下马上来正解
by cn_lemon @ 2017-10-01 20:54:57
@ Caro23333 给你一个数据:
6 1 2 2 3 3 4 3 5 3 6 5 6 然后你把这个图画出来,在写出它的搜索树,模拟数组存储顺序就知道了
by cn_lemon @ 2017-10-01 20:58:20
@Caro23333 当你搜索3号点的时候,你会去搜索4这个度为1的点,并且无法继续向下搜索了,所以你的搜索在4这里出现了第一个叶子节点,所以4这个本来应该是终点的点永远最先进队,满足条件,如果你在搜索过程中输出,就会在搜完3之后把4在中途输出,你就完蛋了
by xunzhen @ 2018-01-03 18:03:29
@cn_lemon 回答得非常好,我本来也不理解
by qwerta @ 2018-07-28 17:17:18
@cn_lemon 谢谢QAQ