一笔画成

2014年5月2日1,5810

来源:http://218.5.5.242:9018/JudgeOnline/problem.php?id=1442

题目描述

一个图能否一笔画成,如果能请你每次都从当前最小编号的点开始画起,如果不行,则输出“no answer”

输入

4
0 1 0 0
1 0 1 1
0 1 0 1
0 1 1 0

输出

1 2 3 4 2

题解

诶,这题是无向图。。

首先用并查集判断图是否连通,这个略过。。

然后图中要有0或2个度为奇数的点

如果是0个,则任意一个点都可以为起点,且为终点。

2个的话当然一个起点一个终点,dfs输出路径,同时保证每条边只走一次,大概这样