A few definitions first:
Definition 1
A graph G = (V, E) is called "dense" if for each pair of non-adjacent vertices u and v, d(u) + d(v) >=n where n = |V| and d(x) denotes the degree of the vertex x.
Definition 2
A "Hamiltonian cycle" on G is a sequence of vertices (v1 v2 ... vn v1) such that vl ≠ vh for all l ≠ h and any neighbor two points is an edge of G.
The problem is: write a program that, given a dense undirected graph G = (V; E) as input (G is a simple graph), determines whether G admits a Hamiltonian cycle on G and outputs that cycle, if there is one, or outputs "N" if there is none.
Warn: 本題有 specialjudge
There are many inputs ended by EOF.
For each input, first line contain an integer n (2 < n < 256), followed several lines containing two integer x, y denoting an edge of the graph G. And an input is ended by a line containing '%' only.
The output file must contain the sequence of vertices that form a Hamiltonian cycle in the form:
v1 v2 ... vn v1
or containing:
N
4 1 2 2 3 2 4 3 4 3 1 % 6 1 2 1 3 1 6 3 2 3 4 5 2 5 4 6 5 6 4 %
1 2 4 3 1 1 3 2 5 4 6 1
Migrated from old NTUJ.
uva 775
| No. | Testdata Range | Score |
|---|