程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva10596 Morning Walk

uva10596 Morning Walk

編輯:C++入門知識

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<iostream>  
#include<cstdio>  
#include<cstring>  
#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<r;i++){ 
            int t1,t2; 
            cin>>t1>>t2; 
            u[t1]++; 
            u[t2]++; 
        } 
        int i; 
        for(i=0;i<n;i++){ 
            if(!u[i] || (u[i]&1)) break; 
        } 
        if(i==n)cout<<"Possible"<<endl; 
        else cout<<"Not Possible"<<endl; 
    } 
    return 0; 

#include<iostream>
#include<cstdio>
#include<cstring>
#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<r;i++){
            int t1,t2;
            cin>>t1>>t2;
            u[t1]++;
            u[t2]++;
        }
        int i;
        for(i=0;i<n;i++){
            if(!u[i] || (u[i]&1)) break;
        }
        if(i==n)cout<<"Possible"<<endl;
        else cout<<"Not Possible"<<endl;
    }
    return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved