国土政务网站建设制度,下载购物app,网络销售招聘,响应式网站高度如何计算作者 张志梅
单位 青岛大学
小丁最近迷恋上一个游戏#xff0c;传说中的“一笔画”游戏。
那么什么是一笔画#xff1f;如下图#xff0c;顾名思义就是一笔可以完成的图。一笔画最基本的要求是在画图的过程中#xff0c;笔不能离开纸#xff0c;且笔所画过的线不能重复…作者 张志梅
单位 青岛大学
小丁最近迷恋上一个游戏传说中的“一笔画”游戏。
那么什么是一笔画如下图顾名思义就是一笔可以完成的图。一笔画最基本的要求是在画图的过程中笔不能离开纸且笔所画过的线不能重复最后画完所有的线便算完成。 虽然小丁喜欢玩这个游戏但有时候花费半天也找不到答案。小丁听说写一个计算机程序便能判断是否可以一笔画图所以他希望善良可爱的你来帮帮他的忙。
快来帮帮弱小可怜又无助的小丁。
评测数据加强啦来验题吧~~
输入格式:
给出图中的节点数N1N1000,编号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那么一个是起点一个是终点。 #includebits/stdc.h
using namespace std;
typedef long long ll;
#define endl \nconst ll N 1e37;
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 txfind(x),tyfind(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 cnt0,sum0;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 t1;//cin t;while(t--)solve();return 0;
}
