Do you know some unexpected and interesting applications of these hamiltonian and eulerian cycles/paths? For example, I have recently learnt about string reconstruction as an eulerian path problem and I was suspised a bit.

So, do you know something similar else?

Given an array $$$a_1,a_2,\dots,a_n$$$, $$$a_i=i$$$ and a permutation of this array $$$p_1,p_2,\dots,p_n$$$. We sort this permutation to get initial array using bubble sort.

Question: how to calculate a number of swaps in $$$O(n)$$$ instead $$$O(n^2)$$$?