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