You are not logged in. Please login at www.codechef.com to post your questions!

×

BIGO04-Editorial

Problem Link :

Practice
Contest

Author: Amrutansu Garanaik , Abhishek Patnaik
Tester: Keshow Sablaka, Amit Das
Editorialist: Amrutansu Garanaik , Amit Kumar Sahu

Difficulty :

Easy

Pre-requisite

Graph theory

Problem :

Given a set of cities and bi-directional roads connecting them. Is it possible to travel through all roads exactly once and come back to the starting point?

Explanation

The problem asks whether there exists an Eulerian circuit in a graph or not. If so, it is possible to traverse all the edges exactly once and come back to starting node. A graph has a Eulerarian circuit if each vertices have even degrees. So, we just have to store the degrees of each node (here the cities) and count whether there is a node with odd degree. If so, print “NO” , otherwise “YES”. Check setter solution for implementation. N.B. The test cases were a bit weak, so some wrong answers also passed the test cases. We are sorry for that. But if your answer gave WA, then it means your answer is definitely wrong. For AC however, it might or might not be wrong.
This question is marked "community wiki".

asked 03 Apr '15, 20:41

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%

edited 04 Apr '15, 13:00


@dragonemperor For euler circuit to exist . The graph should be connected right .? But I got AC by just checking the even degree of every node

link

answered 04 Apr '15, 16:52

ayushtomar's gravatar image

5★ayushtomar
14115
accept rate: 4%

Yes, you are right. For our test cases, we created some graphs using pen and paper and used them to create the test files. Unfortunately all the graphs were connected. Also some wrong answers were accepted because of that.

(06 Apr '15, 00:28) dragonemperor3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,630
×3,741
×15
×4
×3

question asked: 03 Apr '15, 20:41

question was seen: 756 times

last updated: 06 Apr '15, 00:28