TOURISTS - Editorial

editorial
, , , , ,
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.

1 Like
2

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 .

3

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

4

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

5

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][1]

Thanks!
[1]: https://www.codechef.com/viewsolution/12622153

6

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

7

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.

8

@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…

2 Likes
9

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.

10

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

11

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"; }