# Eulerian Tours

Authors: Benjamin Qi, Mihnea Brebenel

Visiting all edges of a graph exactly once.

### Prerequisites

Mentioned in USACO Training ...

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show TagsEuler Tour | |||

CSES | Easy | ## Show TagsEuler Tour |

## Resources

Resources | ||||
---|---|---|---|---|

CPH | ||||

CP2 |

## Implementation

### Mail Delivery

First let's define what an **Eulerian path** is.

An Eulerian path is a path that goes through every edge once.

Similarly, an **Eulerian cycle** is an Eulerian path that starts and ends
with the same node.

An important condition is that a graph can have an Eulerian cycle (not path!) if and only if every node has an even degree.

Now, to find the Eulerian cycle we run a modified DFS. The DFS goes through only unvisited edges and the same edge can be processed multiple times throughout the DFS, so we remove it from the graph at the first visit.

The algorithm described is Hierholzer's Algorithm.

**Time Complexity:** $\mathcal{O}(E)$

C++

#include <bits/stdc++.h>using namespace std;int n, m;vector<vector<pair<int, int>>> g;vector<int> path;vector<bool> seen;void dfs(int node) {while (!g[node].empty()) {

### Teleporters

The condition of existance for an eulerian path in a directed graph is: At most one node has $out_i - in_i=1$ and at most one node has $in_i - out_i=1$. This property is because an Eulerian path or cycle leaves a node the same number of times it enters the node. In a directed geaph the exception are the start node and the end node.

C++

#include <bits/stdc++.h>using namespace std;int n, m;vector<vector<int>> g;vector<int> in, out, path;void dfs(int node) {while (!g[node].empty()) {int son = g[node].back();

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Baltic OI | Easy | ## Show TagsEuler Tour | |||

CF | Easy | ||||

CSA | Normal | ||||

CF | Normal | ## Show TagsEuler Tour | |||

CF | Normal | ## Show TagsEuler Tour | |||

Balkan OI | Normal | ## Show TagsEuler Tour |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!