PrevNext
Has Not Appeared
 0/10

Eulerian Tours

Authors: Benjamin Qi, Mihnea Brebenel

Visiting all edges of a graph exactly once.

Edit This Page

Mentioned in USACO Training ...

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsEuler Tour
CSESEasy
Show TagsEuler Tour

Resources

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: O(E)\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 existence for an eulerian path in a directed graph is: At most one node has outiini=1out_i - in_i=1 and at most one node has iniouti=1in_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 graph 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();

De Bruijn Sequences

Focus Problem – try your best to solve this problem before continuing!

A De Bruijn sequece is a string of minimum length that contains every string of length nn exactly once as a substring, for a fixed alphabet with kk letters. In our case k=2k=2 because we only have 00 and 11.

Let's take a look at some particular cases:

  1. n=2n=2 \rightarrow 00110
  2. n=3n=3 \rightarrow 0001011100

We can visualize the transitions - adding 00 or 11 - using an oriented graph whose nodes contain a string of length n1n-1.

de-bruijn How the graph looks for n=3n=3

An Eulerian path in the above graph represents a valid solution. The starting node has n1n-1 characters and there are knk^n edges that each add one more character, so the length of a De-Bruijn string is kn+n1k^n+n-1.

C++

#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
if (n == 1) {
cout << "10" << endl;
return 0;
}

Problems

StatusSourceProblem NameDifficultyTags
Baltic OIEasy
Show TagsEuler Tour
CFEasy
CSANormal
CFNormal
CFNormal
Show TagsEuler Tour
CFNormal
Show TagsEuler Tour
Balkan OINormal
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!

PrevNext