Description
Problem H
Morning Walk
Time Limit
3 Seconds
Kamal is a Motashota guy. He has got a new job in Chittagong. So, he has moved to Chittagong from Dinajpur. He was getting fatter in Dinajpur as he had no work in his hand there. So, moving to Chittagong has turned to be a blessing for him. Every morning he takes a walk through the hilly roads of charming city Chittagong. He is enjoying this city very much. There are so many roads in Chittagong and 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 help Kamal in 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 from0 to N-1. The second numberR denotes the number of roads (0 ≤ R ≤ 10000). Then there will beR lines each containing two numbersc1 andc2 indicating the intersections connecting a road.
Output
Print a single line containing the text “Possible” without quotes if it is possible for Kamal to visit all the roads exactly once in a single walk otherwise print “Not Possible”.
Sample Input
Output for Sample Input
2 2
0 1
1 0
2 1
0 1
Possible
Not Possible
Problemsetter: Muhammad Abul Hasan
International Islamic University Chittagong
需要注意一点：边不是有向边，两点间可以有多条无向边。
下面是错误且AC代码。。。多连通分支情况不行。。。
算法：判断图是否连通且含欧拉回路就好，所以只要记录点度数是否为零，且是否为偶数即可。当且仅当图连通且所有点度数为偶数，输出Possible :).
[cpp]
#include
#include
#include
#define N 202
using namespace std;
int u[N];
int main(){
int r,n;
while(cin>>n>>r){
memset(u,0,sizeof(u));
for(int i=0;i
cin>>t1>>t2;
u[t1]++;
u[t2]++;
}
int i;
for(i=0;i
}
if(i==n)cout<<"Possible"<
return 0;
}
#include
#include
#include
#define N 202
using namespace std;
int u[N];
int main(){
int r,n;
while(cin>>n>>r){
memset(u,0,sizeof(u));
for(int i=0;i
cin>>t1>>t2;
u[t1]++;
u[t2]++;
}
int i;
for(i=0;i
}
if(i==n)cout<<"Possible"<
return 0;
}