Alexander Hamilton needs your help. He needs to ride around the country and rally the troops, because:
The plan is to fan this spark into a flame.
Though frustrated by the lack of resources provided by the Continental Congress, Hamilton believes:
I'm just like my country - I'm young, scrappy, and hungry, and I am not throwing away my shot.
Undeterred by the might of the British empire, he confidently proclaims:
I may not live to see our glory, but I will gladly join the fight. And when our children tell our story, they’ll tell the story of tonight.
Help Hamilton in his fight against the dreaded red coats by charting a path through a set of checkpoints such that he only visits each checkpoint once and that he returns from where he started (ie.completes a cycle).
Hurry, there is no time to waste! This is your shot! After all:
When you got skin in the game, you stay in the game. But you don’t get a win unless you play in the game. Oh, you get love for it. You get hate for it. You get nothing if you... Wait for it, wait for it, wait.
Input
The input will be a series of graphs in the following format:
N1
Ui1 Uj1
...
%
N2
Ui1 Uj1
...
%
Where Ni is the number of vertices (0
< Ni < 256) and Uih
Uil are integers between 1 and Ni indicating that there exists an edge between vertex Uih and Uil. Each graph is terminated with a %.
Example Input
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
%
Output
For each test case, output a line that must contain the sequence of vertices that form a Hamiltonian cycle in the form:
Ui1 Ui2 ...
If no such path exists, then output:
None
Note: To ensure consistent output, make sure you traverse the neighbors of a vertex in sorted order.
Example Output
1 2 4 3 1
1 2 3 4 5 6 1
Programming Challanges
This is based on 775 - Hamiltonian Cycle problem on the UVa Online Judge.
Submission
To submit your work, follow the same procedure you used for Reading 00:
$ cd path/to/cse-30872-fa18-assignments # Go to assignments repository
$ git checkout master # Make sure we are on master
$ git pull --rebase # Pull any changes from GitLab
$ git checkout -b challenge19 # Create and checkout challenge19 branch
$ $EDITOR challenge19/program.cpp # Edit your code
$ git add challenge19/program.cpp # Stage your changes
$ git commit -m "challenge19: done" # Commit your changes
$ git push -u origin challenge19 # Send changes to GitLab
To check your code, you can use the .scripts/submit.py script or curl:
$ .scripts/submit.py
Submitting challenge19 assignment ...
Submitting challenge19 code ...
Result Success
Score 6.00
Time 0.03
$ curl -F source=@challenge19/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa18/challenge19
{"score": 6, "result": "Success"}
