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