Problem H
|
Morning Walk
|
Time Limit
|
3 Seconds
|
Kamalis aMotashotaguy. He has got a new job inChittagong. So, he has moved toChittagongfromDinajpur. He was getting fatter inDinajpuras he had no work in his hand there. So, moving toChittagonghas turned to be a blessing for him. Every
morning he takes a walk through the hilly roads of charming cityChittagong. He is enjoying this city very much. There are so many roads inChittagongand every morning he takes different paths for his walking. But while choosing a path he makes sure he does
not visit a road twice not even in his way back home. An intersection point of a road is not considered as the part of the road. In a sunny morning, he was thinking about how it would be if he could visit all the roads of the city in a single walk. Your task
is to helpKamalin determining whether it is possible for him or not.
Input
Input will consist of several test cases. Each test case will start with a line containing two numbers. The first number indicates the number of road intersections and is denoted byN(2 ≤ N ≤ 200). The road intersections
are assumed to be numbered from0toN-1. The second numberRdenotes the number of roads (0 ≤ R ≤ 10000). Then there will beRlines each containing two numbersc1andc2indicating
the intersections connecting a road.
Output
Print a single line containing the text “Possible” without quotes if it is possible forKamalto visit all the roads exactly once in a single walk otherwise print “Not Possible”.
Sample Input
|
Output for Sample Input
|
22
0 1
1 0
2 1
0 1
|
Possible
Not Possible
|
Problemsetter: Muhammad Abul Hasan
International Islamic UniversityChittagong
这道题一看觉得是挺简单的欧拉图问题,一想总觉得不对劲,果然卡了很久,对欧拉图一点都不熟悉,代码还参考了别人的,在这里写一下欧拉图的判断
有向图欧拉路或欧拉回路的判定方法:
(1)有向图G为欧拉图(存在欧拉回路),当且仅当G的基图连通,且所有顶点的入度等于出度。
(2)有向图G为半欧拉图(存在欧拉道路),当且仅当G的基图连通,且存在顶点u的入度比出度大1、v的入度比出度小1,其它所有顶点的入度等于出度。
无向图的欧拉图判定方法:
(1) 图连通。
(2)所有的点的度数(出度和入度之和)为偶数。
#include<iostream>
#include<cstring>
using namespace std;
int du[210];
int bin[210];
int findx(int t)
{
int r=t;
while(bin[r]!=r)
{
r=bin[r];
}
return r;
}
void mergex(int x,int y)
{
int fx,fy;
fx=findx(x),fy=findx(y);
if(fx!=fy)
{
bin[fx]=fy;
}
}
int main()
{
int n,r;
while(cin>>n>>r)
{
if(r==0)
{
cout<<"Not Possible"<<endl;
continue;
}
memset(du,0,sizeof(du));
int i,j,k;
for(i=0;i<n;i++)
bin[i]=i;
for(i=0;i<r;i++)
{
cin>>j>>k;
du[j]++;
du[k]++;
mergex(j,k);
}
int tag=1,t=0;
for(i=0;i<n;i++)
if(bin[i]==i) t++;
for(i=0;i<n;i++)
{
if((du[i])%2!=0)
{
tag=0;
break;
}
}
if(tag&&t==1) cout<<"Possible"<<endl;
else cout<<"Not Possible"<<endl;
}
return 0;
}
分享到:
相关推荐
广东省博罗县泰美中学七年级英语下册 Module 10 Unit 2 This morning we took a walk导学案(无答案)(新版)外研版
本课件是一个优秀的英语ppt课件,课件中的相关知识点,帮助老师更好的完成本科的...该文档为This morning we took a walk A holiday journey PPT课件,是一份很不错的参考资料,具有较高参考价值,感兴趣的可以下载看看
本课件是一个优秀的英语ppt课件,课件中的相关知识点,帮助老师更好的完成本科...该文档为This morning we took a walk A holiday journey PPT课件2,是一份很不错的参考资料,具有较高参考价值,感兴趣的可以下载看看
Web Morning Reading Comprehension Passages With Key
2019 Mock Exam A Morning Session 这份文件是2019年CFA考试考纲内容的资料,适用于6月份和12月份的考试,比直接看原版书教材更高效便捷,同时每一个知识点在里面都有重难点标注出来,特别好用。
一款开源的商城系统,希望大家踊跃下载.哈哈哈哈哈哈哈哈和
程序比较完善,功能强大的韩国的morningmall商城
Morning Notes.pdf
2017CFA一级_level_I_mock_exam_morning
2017CFA一级_level_I_mock_exam_morning
本课件是一个优秀的英语ppt课件,课件中的相关知识点,帮助老师更好的完成本科...该文档为This morning we took a walk A holiday journey PPT课件3,是一份很不错的参考资料,具有较高参考价值,感兴趣的可以下载看看
Morning UI是一套桌面端UI组件库,基于。 为什么要用 Morning UI? 基于Vue.js,开箱即用,简单易学 超过80个组件 强大的表单组件,可用于生成复杂数据结构(包括对象和数组等) 安装 npm install morning-ui --save ...
Wordpress Urban Morning模板
外研社七年级上册英语Good,morning,Miss,Zhou.doc
2019年七年级英语上册StarterUnit1Goodmorning知识点总结素材新版人教新目标版202004162136
Pladisei in the morning!
Morning Research Focus.pdf
七年级上册Starter Unit 1 Good morning同步练习题及答案精选.doc
Wordpress MORNING年度佳6
MORNING CONSULT-比会议室更大:对CEO的角-期待(英文)-2020.9-34页精品报告2020.pdf