Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Take a Walk
Description A walk v_{0}e_{1}v_{1}e_{2}v_{2}...v_{k-1}e_{k}v_{k}whose terms are alternately vertices and edges such that, for 1 ≤ v_{i-1} and v. If the edges _{i}e_{1}, e_{2}, ... , e of the walk are distinct, then _{k}W is called a trail. A trail with v_{0} ≠ v is an _{k}open trail. If W is a closed walk. A tour of G is a closed walk of G that includes every edge of G at least once.Write a program that determines whether for a graph - there exists an open trail that includes every edge of G, or not; and
- there exists a tour that includes every edge of G exactly once, or not
where graph Input The input file consists of several test cases, each with a case number, the set of vertices in a graph, and the set of edges in the graph, as shown in the samples. Assume the vertices are single letters only. Output For each of the test cases, output "Yes" if the graph has at least one open trail that includes every edge of the graph, and "No", if not; and output "Yes" if the graph has at least one tour that includes every edge of the graph exactly once, and "No" if not. Sample Input Case 1: { a, b, c, d, e } { (a,b), (b,c), (c,d), (d,a), (b,e), (c,e) } Case 2: { a, b, c, d, e } { (a,b), (a,c), (b,e), (b,d), (b,c), (d,c), (d,e), (d,e), (e,c) } Case 3: { A, B, c, d } { (A,B), (c,d) } Sample Output Yes No No Yes No No Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator