URAL 1077 - Travelling tours

Solution

First, the number of tours = |E| - |V| + |C|, where |C| is the number of connected component.
The algorithm will explain it.

For each connected component, find an arbitrary spanning tree.
For each back edge (u,v) in the spanning tree, the back edge (u,v) + the tree edge connecting u to v forms a cycle.
Since the back edge is used only in this cycle, it is a valid tour.

Hence the number of tours = the number of back edges = |E| - number of tree edges = |E| - |V| + |C|.

This is optimal because after we create a spanning tree, each cycle must include some back edges.