Editorial for TOURIST

Can anyone explain the approach to solve TOURIST (JAN Long) ?

Consider the corresponding undirected graph. If there is an Euler circuit in this graph, then, the original graph can be transformed into it through redirection. The Euler circuit gives the order in which the edges are to be traversed.

1 Like

check the euler ckt existence in the undirected graph so that transformation can occurs…

1 Like

This question is about Eulerian Circuit .I solved it as follows :

  1. Checking whether the circuit exists or not:
    I considered the edges as undirected and checked the 2 requirements :
    i) each vertex has an even degree
    ii) the whole graph is connected

  2. Creating the circuit : I used Hierholzer’s algorithm which runs in O(|E|) to determine the circuit and then changed the corresponding edges if necessary or kept them the same.

My Solution

6 Likes

First see how to traverse when you are given directed graph but you have to change it in such a way that behave like a undirected graph! I mean you have to know the basic idea of DFS, Euler Circuit and Traversal in this case! Here is question which is similar or explain this Except Euler! Chef and Reverse

First, check if the Euler cycle exists ignoring the directions( that is considering it as undirected graph) by using the following facts :

1.An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component. To check if its a single connected component apply BFS or DFS alorithm on any one vertex and if every vertex can be visited from your chosen vertex . Then , its singly connected.

Then , if eulerian cycle exists on the undirected graph, you have to redirect certain paths to solve the problem which can be done as explained by above users.

I used the same algorithms as discussed here, but,i don’t have any idea why am i getting WA in 2 test cases 1 apiece in both the subtasks :(. Please can anyone help me?

Link- https://www.codechef.com/viewsolution/12600300

@anuraag_s2 Your code gives yes for this test case :


9 9
1 8
2 4
3 9
4 3
5 1
6 2
7 5
8 7
9 6

while the answer should be no.

Here’s a nice explanation to trace the euler path.
http://www.graph-magics.com/articles/euler.php

Hope you find this well commented code useful - atulac - TOURIST Solution - 100 points

1 Like

I have a question. What will be the maximum number of edges when all the nodes i.e 100000 will be present for a graph containing euler circuit?
As i was looking at this solution Link he used the maximum value 102936.

Can anybody help me with subtask 1 , I couldn’t get where is my code failing :frowning:

My solution: https://www.codechef.com/viewsolution/12552062

I used the same results. I also used Fleury’s algorithm. Could someone point out the flaw?

hi how to generate the link for the solution that i have done. Please help me.

@sagar2009kumsr

  • Go to Ideone.com
  • Paste your code there.
  • Select the language.
  • Click on Run.
  • Your code will be compiled and the link will be generated .

@ashutosh_cric, I adjusted for this case in a newer solution. https://www.codechef.com/viewsolution/12554634

The first test case still fails. Any idea why? In this solution, I consider the case wherein there are multiple roads between two vertices.

@ashutosh_cric, I adjusted for this case in a newer solution. https://www.codechef.com/viewsolution/12554634

The first test case still fails. Any idea why? In this solution, I consider the case wherein there are multiple roads between two vertices.

Thanks a lot! @aky1994

@nipungarg59 Thanks,for your help.
I didnt check if the graph was connected or not . Time to leave this planet ;___;

Thanks a ton buddy! Helped a lot.