X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/8b3b322359561c6c1ba4d00927400c0e5c6eecf2..2e215ca91f5ba292166531b57c0ecddf10b1f8f7:/dsf.c

diff --git a/dsf.c b/dsf.c
index 32179a6..aa22392 100644
--- a/dsf.c
+++ b/dsf.c
@@ -161,7 +161,21 @@ void edsf_merge(int *dsf, int v1, int v2, int inverse)
         assert(!inverse);
     else {
 	assert(inverse == 0 || inverse == 1);
-	if ((dsf[v2] >> 2) > (dsf[v1] >> 2)) {
+	/*
+	 * We always make the smaller of v1 and v2 the new canonical
+	 * element. This ensures that the canonical element of any
+	 * class in this structure is always the first element in
+	 * it. 'Keen' depends critically on this property.
+	 *
+	 * (Jonas Koelker previously had this code choosing which
+	 * way round to connect the trees by examining the sizes of
+	 * the classes being merged, so that the root of the
+	 * larger-sized class became the new root. This gives better
+	 * asymptotic performance, but I've changed it to do it this
+	 * way because I like having a deterministic canonical
+	 * element.)
+	 */
+	if (v1 > v2) {
 	    int v3 = v1;
 	    v1 = v2;
 	    v2 = v3;