What about keeping track of the size of each of the sets?
Then, when doing a union, if the root of both is the same (i.e. a cycle) and the root's size equals the sum of all the points in your problem, include that edge and stop, otherwise continue as per usual.
Warning:
Note that a simple Union-Find implementation is likely to end you up with minimum spanning tree rather than a hamiltonian cycle. You need to make sure you pick appropriate edges - I'll assume you've figured that out, or, if not, I'll leave it to you.
Elaboration:
The Union
for your problem should look something like: (derived from Wikipedia)
(returning false
or true
to indicate whether we should add the edge)
boolean Union(x, y)
xRoot = Find(x)
yRoot = Find(y)
if xRoot == yRoot
return false
// merge xRoot and yRoot
xRoot.parent = yRoot
return true
(the proper merge (for efficiency) is a little more complicated - you should compare the depths and pick the deepest one as the parent, see Wikipedia for details)
Now, my suggestion:
Create a size
variable for each node, initialized to 1
, and then the Union
function:
boolean Union(x, y)
xRoot = Find(x)
yRoot = Find(y)
if xRoot == yRoot
// check if it's the last node
if xRoot.size == pointCount
done = true
return true
else
return false
// merge xRoot and yRoot
xRoot.parent = yRoot
yRoot.size += xRoot.size
return true
Example:
Points:
1---2
|\ |
| \ |
| \|
4---3
There are 4 points, thus pointCount = 4
Starting off: (size
appears under node)
1 2 3 4
1 1 1 1
Union 1
and 2
:
1 3 4
2 1 1
|
2
1
Union 3
and 2
:
3 4
3 1
|
1
2
|
2
1
Union 3
and 1
:
The common root is 3
(thus xRoot == yRoot
is true) and xRoot.size(3)
!= pointCount(4)
, thus we return false (don't add the edge).
Union 3
and 4
:
4
4
|
3
3
|
1
2
|
2
1
Union 4
and 1
:
The common root is 4
(thus xRoot == yRoot
is true) and xRoot.size(4)
== pointCount(4)
, thus we return true (add the edge) and we set the flag to indicate that we're done.