pta 一笔画

pta 一笔画

小丁最近迷恋上一个游戏，传说中的“一笔画”游戏。

那么什么是一笔画？如下图，顾名思义就是一笔可以完成的图。一笔画最基本的要求是在画图的过程中，笔不能离开纸，且笔所画过的线不能重复，最后画完所有的线便算完成。

虽然小丁喜欢玩这个游戏，但有时候花费半天也找不到答案。小丁听说写一个计算机程序便能判断是否可以一笔画图，所以他希望善良可爱的你来帮帮他的忙。

快来帮帮弱小，可怜，又无助的小丁。

输入格式:

给出图中的节点数N（1<=N<=1000,编号1-N）和边数M；随后M行给出存在边的两个节点的编号。

输出格式:

能够一笔画的图输出Y，否则输出N。

输入样例1:

3 2
1 2
2 3

输出样例1:

Y

输入样例2:

4 3
1 2
1 3
1 4

输出样例2:

N

 代码如下

#include
using namespace std;
int xia[1002][1003] = { 0 };
int n, m,con=0;
int* tips;
void dfs(int k, int n)
{
	tips[k] = 1;
	con++;
	for (int i = 1; i <= n; i++) {
		if (xia[k][i] != 0 && tips[i] == 0) {//如果还有路径就接着向下走
			dfs(i, n);
			break;
		}
	}//走完就判断下是不是全走完了，全走完就直接退出，没有就接着递归
	if (con == n) { cout << "Y"; exit(0); }
	con--;
	tips[k] = 0;
	
}
int main() {

	cin >> n >> m;
	tips = new int[n + 2]();
	int a1, a2;
	for (int i = 0; i < m; i++) {
		cin >> a1 >> a2;
		xia[a1][a2]++;
		xia[a2][a1]++;
	}//连接
	for (int i = 1; i <= n; i++) {
		dfs(i, n);
	}
	cout << "N";
}