AlmostEulerianGraph
SRM 672 · 2015-08-31 · by Zlobober
Problem Statement
In this problem we consider undirected graphs on n vertices. The vertices are numbered 0 through n-1. The graphs are simple: they do not contain self-loops, and each pair of vertices is directly connected using at most one edge.
An undirected connected graph is called Eulerian if there is a closed walk that contains each edge of the graph exactly once. (A closed walk is a sequence of consecutive edges that starts and ends in the same vertex.)
Bomboslav invented his own kind of graphs that he calls almost-Eulerian. All Eulerian graphs are also almost-Eulerian. Additionally, a graph is also almost-Eulerian if there exists a way to add or remove exactly one edge to/from it in such a way that the resulting graph becomes Eulerian. (Note that if you are adding an edge, you are not allowed to create a self-loop and you are not allowed to connect vertices that are already connected by another edge.)
After removing the selected edge, it becomes Eulerian.
Bomboslav is now interested in calculating the number X of different almost-Eulerian graphs on n vertices. Two graphs are considered different if there exists a pair of indices 0 <= i < j <= n-1 such that the edge (i, j) is present in exactly one of those two graphs. Compute and return the value (X modulo 1,000,000,007).
Constraints
- n will be between 2 and 2000, inclusive.
3 Returns: 4
All almost-Eulerian graphs are shown in the picture below.
2 Returns: 0
Note that an empty graph on 2 vertices isn't Eulerian since it is disconnected.
42 Returns: 29010676
4 Returns: 21
5 Returns: 418
Submissions are judged against all 25 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AlmostEulerianGraph with a public method int calculateGraphs(int n) · 25 test cases · 2 s / 256 MB per case