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

×

Problem in understanding tourist editorial

Can anyone explain implementation details of Tourists(Euler circuits) problem in january long challenge. I couldn't understand from editorails.

asked 23 Jan '17, 19:39

arpit728's gravatar image

2★arpit728
6831460
accept rate: 10%

edited 27 Feb, 19:26


First let's consider the cases where the answer is going to be "NO":

  • The graph is not connected (more than 1 components)
  • There exists vertices (or a single vertex) with odd degree

If either of the above is true, just print NO otherwise, create an adjacency list for an undirected graph (i.e. for an edge u,v add v to u's list and vice versa) and use the following algorithm:

find_tour(u):

for each edge e=(u,v) in E:(vertices adjacent to u)
     remove v from u's list
     remove u from v's list
     add edge u,v to a set or vector (which contains the tour sequence)
     findtour(v)

and then print the edges in the set or vector you inserted the edges according to the order in the input

for full implementation, check my submission here

link

answered 23 Jan '17, 21:08

swetankmodi's gravatar image

6★swetankmodi ♦♦
6008
accept rate: 15%

implementation details it’s behavior produced by the code which may be relied on by consuming code. Though that behavior not specified by spec the code is written to hence Assignment Moz We will break it to consuming code that’s why it’s bad to rely on them

link

answered 25 Jan '17, 13:29

sharlyn001's gravatar image

0★sharlyn001
1
accept rate: 0%

Here is my simple DFS solution! I just used a reverse edge concept in which i visited the edge and whenever we encounter the reverse edge in DFS, then i just simply visit this by using map<> STL in C++.

In my solution I assigned reverse edge as 1 and directed edge as 0. So in Check() function whenever i visit reverse edge i just visit this by MAP<>.

In printing side whenever i encounter reverse edge, then i simply reverse it. Only! I hope this will be simple from Editorial solution!

If you wanna ask more about this, then freely comment your doubt!

See this code!

link

answered 25 Jan '17, 19:25

bansal1232's gravatar image

5★bansal1232
2.8k1418
accept rate: 16%

@swetankmodi Thanks :) It really helped me in understanding the solution.

link

answered 25 Jan '17, 23:02

deepansh_946's gravatar image

2★deepansh_946
466
accept rate: 0%

1

welcome! :)

(01 Feb '17, 00:28) swetankmodi ♦♦6★
Answer is hidden as author is suspended. Click here to view.

answered 27 Feb, 12:39

harrymorgan1's gravatar image

0★harrymorgan1
(suspended)
accept rate: 0%

The purposes of this website is to deliver the best online system resource for the poor persons and rural people either incapacity person in metropolitan world. Leather Coats for Men

link

answered 20 Jun, 17:39

rachellemarie's gravatar image

0★rachellemarie
1
accept rate: 0%

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:

×1,185
×72

question asked: 23 Jan '17, 19:39

question was seen: 1,209 times

last updated: 20 Jun, 17:39