×

# TOURISTS - Editorial

Tester: Istvan Nagy
Editorialist: Misha Chorniy

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".

6★mgch
3451128
accept rate: 23%

19.7k350498541

 2 @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.. answered 23 Jan '17, 23:12 57●6 accept rate: 0%
 0 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 '17, 01:42 11 accept rate: 0%
 0 can u please provide the second last test case of subtask 2 , it was creating a lot of problem during the contest? answered 22 Jan '17, 05:03 261●4 accept rate: 11%
 0 @jragarwal X ^ X = 0, 0 ^ Y = Y bro. Then that xor is doing it there. answered 22 Jan '17, 13:04 1 accept rate: 0%
 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! answered 22 Jan '17, 15:09 4★bluefog 11●1 accept rate: 0%
 0 Some one please explain the euler dfs function given in setter's solution more clearly. Thanks in advance. answered 22 Jan '17, 15:24 46●6 accept rate: 0%
 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. answered 23 Jan '17, 07:50 11●1 accept rate: 0%
 0 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. answered 23 Jan '17, 23:47 46●6 accept rate: 0%
 0 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 answered 24 Jan '17, 15:16 19●1 accept rate: 0%

Can Some Plaease Help and see why my solution fails 

# include <bits stdc++.h="">

using namespace std; const int N = 1e6;

# define ll long long

set<ll>Adj[N]; vector < pair <ll,ll> > Ans; bool vis[N]; void dfs(ll s) { vis[s]=true; for(auto i : Adj[s]) if(!vis[i]) dfs(i); } void euler(ll s) { while(!Adj[s].empty()) { ll to=*Adj[s].begin(); Adj[s].erase(to);Adj[to].erase(s); Ans.push_back({s,to}); euler(to); } } int main() { ll v,e; cin>>v>>e; for(int i=0,x,y;i<e;i++) {="" cin="">>x>>y; Adj[x].insert(y); Adj[y].insert(x); } dfs(1); for(int i=1;i<=v;i++) if(Adj[i].size()&1 || !vis[i]) {cout<<"NO\n";return 0;} euler(1); cout<<"YES\n"; for(auto i : Ans) cout<<i.first<<" "<<i.second<<"\n"; }

01
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,480
×3,705
×1,197
×125
×16
×5

question asked: 19 Jan '17, 05:47

question was seen: 3,744 times

last updated: 30 May '18, 10:42