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

×

TOURISTS - Editorial

1
1

Practice
Contest

Author: Satyaki Upadhyay
Tester: Istvan Nagy
Editorialist: Misha Chorniy

Difficulty:

Easy

Pre-Requisites:

graphs, Euler Circuits

Problem Statement

Given an directed graph, orient each edge in such way that exists way which going over all edges and passes on each edge only once from every node and visits all nodes at least once.

Quick Explanation

We need to check whether is given graph exists Euler Circuit and if it's connected. In the positive case, such tour as in the statement exists.

Explanation

Assume that graph is undirected, and we need to direct every edge in it. If the graph is not connected, then road network in the kingdom of Mancunia can not be tourist-friendly in any way. Because no one tour can visit all cities.

Consider desired orientation of edges, and path from some city $s$, $(u_{1}, u_{2}), (u_{2}, u_{3}), .... (u_{E-1}, u_{E}), (u_{E}, u_{1})$. What we can say about this path, it passes over all cities, so if we rotate this sequence, we can obtain path which satisfied the statement for any city. Denote $in_{a}$, $out_{a}$ - indegree and outdegree for city $a$ respectively. In the path, how many times we will enter the city, as many time we will leave him, so $in_{a} = out_{a}$, but this criterion is very well-known in Graphs Theory, it's criteria of existing of Euler Circuit. As we have the undirected graph, we need to check, if every node has even degree, this one is enough for existing of Euler Circuit.

How to find Euler Circuit in the graph? You can read about algorithms here. Let's write some code for this problem here using Hierholzer's algorithm:

S[v] - set of adjacent nodes to v if graph is undirected DFS(v) //recursive function while !S[v].empty() //While exists undirected edges from node v to = minimalValue(S[v]) //Choose any undirected edge S[v].erase(to); //Erase edge (v, to) S[to].erase(v); //Orient edge in direction (v->to) DFS(to)

After finding of the circuit, let's orient edges in that order.

The overall complexity of this solution is $O(N+E)$ or $O((N+E) log N)$

Solution:

Setter's solution can be found here
Tester's solution can be found here

Please feel free to post comments if anything is not clear to you.

This question is marked "community wiki".

asked 19 Jan, 05:47

mgch's gravatar image

7★mgch
210514
accept rate: 12%

edited 19 Jan, 20:35

admin's gravatar image

0★admin ♦♦
17.4k347487515


@deepansh_946 I think inserting printfs and understanding helps. adj[j] refers to the set of edges incident at vertex j. When you do a dfs with a starting vertex j, you pick its incident edges one by one, and check whether the connectivity is outward. That means v != edgeList[e].first, e is the edge incident on v, if this edge has to be leaving v, then edgeList[e].first must be equal to v, if it isn't, then you swap the vertices which are at the ends of that edge, which essentially means you're changing the edge direction. In short, you're doing a dfs with a starting vertex, picking up the edges incident on it, before proceeding with the regular dfs, you check if the incident edge is in the same direction as you're traversing, if not, swap the ends of the edge! Hope this helps..

link

answered 23 Jan, 23:12

abhidoeslinux's gravatar image

2★abhidoeslinux
476
accept rate: 0%

edited 23 Jan, 23:13

Can you Please explain reason for Xoring or simply the euler_dfs function more clearly . I couldn't understand the function . It does one more thing picking up edges based on node number which has no connection to edge number .

link
This answer is marked "community wiki".

answered 22 Jan, 01:42

jragarwal's gravatar image

2★jragarwal
11
accept rate: 0%

can u please provide the second last test case of subtask 2 , it was creating a lot of problem during the contest?

link

answered 22 Jan, 05:03

ayush_agrawal_'s gravatar image

4★ayush_agrawal_
2264
accept rate: 5%

@jragarwal X ^ X = 0, 0 ^ Y = Y bro. Then that xor is doing it there.

link

answered 22 Jan, 13:04

zlhagvaasuren's gravatar image

3★zlhagvaasuren
1
accept rate: 0%

My submission for this problem fails to finish in time for subtasks 2, 8 and 2, 10. Can someone guide me to the failing testcase for this submission : Submission for TOURISTS

Thanks!

link

answered 22 Jan, 15:09

bluefog's gravatar image

4★bluefog
111
accept rate: 0%

Some one please explain the euler dfs function given in setter's solution more clearly. Thanks in advance.

link

answered 22 Jan, 15:24

deepansh_946's gravatar image

2★deepansh_946
456
accept rate: 0%

In euler_dfs function in setters solution, why 'while' is used, i used a similar approach with 'if', it gave WA on second last case, now when i change it to 'while' it is giving AC. @satyaki3794 my 'if' submission 20 points solution

my 'while' submission 100 points solution

As per my understanding of euler circuit 'if' should be used.

link

answered 23 Jan, 07:50

pk_codechef's gravatar image

3★pk_codechef
111
accept rate: 0%

edited 23 Jan, 07:55

Thanks @abhidoeslinux . My another doubt is that why we are xoring the values? Is there any other way for that? Why or Why not?

Also I want to confirm that after checking the if condition of outward edges we are erasing the edges as we are moving through them. Correct me if i am wrong.

link

answered 23 Jan, 23:47

deepansh_946's gravatar image

2★deepansh_946
456
accept rate: 0%

edited 23 Jan, 23:52

Both tester's and setter's solution are giving wrong output for this testcase

4 8
1 2
2 3
3 4
4 1
3 2
1 4
1 3
2 4

There answer is

YES
1 2
2 3
3 4
1 4
2 3
4 1
3 1
4 2

here 2 3 is getting repeated

The answer will be yes but they are printing the wrong edges @admin @satyaki3794

link

answered 24 Jan, 15:16

vinayak_1's gravatar image

4★vinayak_1
191
accept rate: 0%

edited 25 Jan, 13:45

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:

×12,340
×2,686
×967
×123
×16
×5

question asked: 19 Jan, 05:47

question was seen: 2,413 times

last updated: 25 Jan, 13:45