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

题目要求：

判定是否能一笔画完所有的路径，而且经过所有的点。

思路：

用并查集判断所有点是否能一笔画到。

记录所有的点经过的次数，只有两种情况才能一笔画完：

1、如果任何点都是偶数且不为0，代表从任何起点都能一笔画完。

2、如果只有有两个奇数，其余都是偶数且不为0，那么一个是起点，一个是终点。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"const ll N = 1e3+7;
ll n,m;
ll v[N],value[N];ll find(ll x){return v[x] == x ? x : v[x] = find(v[x]);
}void bing(ll x,ll y){ll tx=find(x),ty=find(y);if(tx > ty)swap(tx,ty);v[ty]=tx;
}void solve(){cin >> n >> m;memset(value,0,sizeof value);for(ll i = 1 ; i <= n ; i ++)v[i]=i;while(m --){ll x,y;cin >> x >> y;if(find(x) != find(y))bing(x,y);value[x]++;value[y]++;}ll cnt=0,sum=0;for(ll i = 1 ; i <= n ; i ++){v[i]=find(v[i]);if(v[i] == i)cnt++;if(value[i]&1)sum++;}if(cnt == 1 && (sum == 2 || sum == 0))cout << "Y" << endl;else cout << "N" << endl;return;
}int main(){ll t=1;//cin >> t;while(t--)solve();return 0;
}

这篇关于PTA一笔画的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---