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

Thanks a lot! @aky1994

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

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

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

1 Like

Thanks a ton buddy! Helped a lot.

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 .

Hi there, in the very first test-case the input is like :

2 2
1 2
2 1

your code’s output is:

YES
1 2

I guess you’re not printing the required edges.

Hi there, you’re not printing the edges in the required order.
Your algorithm seems to be correct. Consider the input:

2 2
2 1
1 2

Your code prints

YES
1 2
2 1

Thus the order is not as in the input.