Problem in understanding tourist editorial

general
,
1

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

1 Like
2

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

2 Likes
3

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

4

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!

5

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

6

Thanks for posting this info. I just want to let you know that I just check out your site 70-532 dumps and I find it very interesting and informative. I can’t wait to read lots of your posts.

7

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

8

welcome! :slight_smile:

1 Like