Author: Satyaki Upadhyay Difficulty:Easy PreRequisites:graphs, Euler Circuits Problem StatementGiven 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 ExplanationWe 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. ExplanationAssume 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 touristfriendly 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_{E1}, 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 wellknown 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:
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 Please feel free to post comments if anything is not clear to you.
This question is marked "community wiki".
asked 19 Jan '17, 05:47

@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

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

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

@jragarwal X ^ X = 0, 0 ^ Y = Y bro. Then that xor is doing it there. answered 22 Jan '17, 13:04

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

Some one please explain the euler dfs function given in setter's solution more clearly. Thanks in advance. answered 22 Jan '17, 15:24

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

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

Both tester's and setter's solution are giving wrong output for this testcase
There answer is
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

Can Some Plaease Help and see why my solution fails ` include <bits stdc++.h="">using namespace std; const int N = 1e6; define ll long longset<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"; } ` answered 30 May '18, 10:42
