uva 10596 - Morning Walk
Morning Walk
Time Limit
3 Seconds
Kamal is aMotashota guy. He has got a new job in Chittagong. So, he has moved to Chittagong fromDinajpur. 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 helpKamal 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 number R denotes the number of roads (0 ≤ R ≤ 10000). Then there will beR lines each containing two numbers c1 andc2 indicating the intersections connecting a road.
Output
Print a single line containing the text “Possible” without quotes if it is possible forKamal 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 UniversityChittagong
회색 달걀이 아픈 제목은 그의 예시를 보면 방향도가 있는 것 같고, 다른 사람의 문제풀이 보고서를 보면 모두 무방향도라고 한다.
무방향도의 오라 회로 문제, 조건은 연통도이고 모든 노드의 도수는 짝수이다
#include <stdio.h>
#define size 210
int num,f,n,visit[size],map[size][size],degree[size];
int dfs(int x)
{int i;
for (i=0;i<n;i++)
if ((visit[i]==1)&&(map[x][i]==1))
{visit[i]=0; ++num;
dfs(i);
}
};
int main()
{int i,j,r,x,y;
while (scanf("%d%d",&n,&r)!=EOF)
{
for (i=0;i<n;i++)
for (j=0;j<n;j++)
map[i][j]=0;
for (i=0;i<n;i++)
{visit[i]=1; degree[i]=0;}
for (i=1;i<=r;i++)
{scanf("%d%d",&x,&y);
map[x][y]=1;
++degree[x];
++degree[y];
}
if (r>0) f=1; else f=0;
for (i=0;i<n;i++)
if (degree[i]%2==1) {f=0;break;}
if (f) {num=1; visit[0]=0; dfs(0); // visit[n-1];dfs(n-1); , 0 , 0 , 。 .....
if (num!=n) f=0;
}
if (f) printf("Possible
");
else printf("Not Possible
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 1017 A Mathematical Curiosity(문제 해결 보고서)바보 B원에서 전재하다 Problem Description Given two integers n and m, count the number of pairs of integers (a,b) such that 0 < a...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.