# UVa 10735

## Summary

Given a graph ${\displaystyle G}$, which contains both directed edges and undirected edges, find a closed path in it, in which each edge is included exactly once.

## Explanation

Recall, when Euler tour exists in a directed graph: the underlying undirected graph is connected, and the in-degree of each vertex is equal to the out-degree.

In this problem, some of the graph's edges may be undirected. If we can orient them in such a way, that the in-degree of each vertex will be equal to its out-degree, then the problem will be reduced to finding a tour in a directed graph. Such orientation can be found by solving the following bipartite matching problem.

Construct a bipartite graph ${\displaystyle H}$. In one partition put all edges (both directed and undirected) of ${\displaystyle G}$, and the other partition contains ${\displaystyle G}$'s vertices. For every edge we have to know, which of its two endpoints is the head. So, connect every object (edge of ${\displaystyle G}$) in the first partition with its ${\displaystyle G}$'s endpoints in the second partition.

We'll be finding a matching in this graph. If an undirected edge ${\displaystyle e=(u,v)}$ of ${\displaystyle G}$ will be matched with ${\displaystyle v}$, it means, that in the final directed graph, the edge ${\displaystyle e}$ will go from vertex ${\displaystyle u}$ to vertex ${\displaystyle v}$.

Each matched ${\displaystyle H}$'s edge of ${\displaystyle (e,v)}$ will contribute to the in-degree of vertex ${\displaystyle v}$ in the directed graph, and unmatched edge ${\displaystyle (e,u)}$ contributes to the out-degree of ${\displaystyle u}$.

Since we want to make the in-degree and out-degree of each vertex equal, each vertex must have an equal number of matched and unmatched edges in ${\displaystyle H}$. Additionally, each directed edge has to be matched with its respective head from ${\displaystyle G}$.

After finding a matching in ${\displaystyle H}$, satisfying the outlined constraints, we can assign direction to each undirected ${\displaystyle G}$'s edge and find Euler tour is the resulting directed graph with any standard algorithm. If a matching doesn't exist, there will be no Euler tour in the original graph.

```2
6 8
1 3 U
1 4 U
2 4 U
2 5 D
3 4 D
4 5 U
5 6 D
5 6 U
4 4
1 2 D
1 4 D
2 3 U
3 4 U
```

## Output

```1 3 4 2 5 6 5 4 1

No euler circuit exist
```