作者 张志梅
单位 青岛大学
小丁最近迷恋上一个游戏，传说中的“一笔画”游戏。
那么什么是一笔画？如下图，顾名思义就是一笔可以完成的图。一笔画最基本的要求是在画图的过程中，笔不能离开纸，且笔所画过的线不能重复，最后画完所有的线便算完成。
虽然小丁喜欢玩这个游戏，但有时候花费半天也找不到答案。小丁听说写一个计算机程序便能判断是否可以一笔画图，所以他希望善良可爱的你来帮帮他的忙。
快来帮帮弱小，可怜，又无助的小丁。
评测数据加强啦，来验题吧~~
输入格式:
给出图中的节点数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;
}
