+ edsf_merge(dsf, v1, v2, FALSE);
+}
+
+int dsf_size(int *dsf, int index) {
+ return dsf[dsf_canonify(dsf, index)] >> 2;
+}
+
+int edsf_canonify(int *dsf, int index, int *inverse_return)
+{
+ int start_index = index, canonical_index;
+ int inverse = 0;
+
+/* fprintf(stderr, "dsf = %p\n", dsf); */
+/* fprintf(stderr, "Canonify %2d\n", index); */
+
+ assert(index >= 0);
+
+ /* Find the index of the canonical element of the 'equivalence class' of
+ * which start_index is a member, and figure out whether start_index is the
+ * same as or inverse to that. */
+ while ((dsf[index] & 2) == 0) {
+ inverse ^= (dsf[index] & 1);
+ index = dsf[index] >> 2;
+/* fprintf(stderr, "index = %2d, ", index); */
+/* fprintf(stderr, "inverse = %d\n", inverse); */
+ }
+ canonical_index = index;
+
+ if (inverse_return)
+ *inverse_return = inverse;
+
+ /* Update every member of this 'equivalence class' to point directly at the
+ * canonical member. */
+ index = start_index;
+ while (index != canonical_index) {
+ int nextindex = dsf[index] >> 2;
+ int nextinverse = inverse ^ (dsf[index] & 1);
+ dsf[index] = (canonical_index << 2) | inverse;
+ inverse = nextinverse;
+ index = nextindex;
+ }
+
+ assert(inverse == 0);
+
+/* fprintf(stderr, "Return %2d\n", index); */
+
+ return index;
+}
+
+void edsf_merge(int *dsf, int v1, int v2, int inverse)
+{
+ int i1, i2;
+
+/* fprintf(stderr, "dsf = %p\n", dsf); */
+/* fprintf(stderr, "Merge [%2d,%2d], %d\n", v1, v2, inverse); */
+
+ v1 = edsf_canonify(dsf, v1, &i1);
+ assert(dsf[v1] & 2);
+ inverse ^= i1;
+ v2 = edsf_canonify(dsf, v2, &i2);
+ assert(dsf[v2] & 2);
+ inverse ^= i2;
+
+/* fprintf(stderr, "Doing [%2d,%2d], %d\n", v1, v2, inverse); */
+
+ if (v1 == v2)
+ assert(!inverse);
+ else {
+ assert(inverse == 0 || inverse == 1);
+ if ((dsf[v2] >> 2) > (dsf[v1] >> 2)) {
+ int v3 = v1;
+ v1 = v2;
+ v2 = v3;
+ }
+ dsf[v1] += (dsf[v2] >> 2) << 2;
+ dsf[v2] = (v1 << 2) | !!inverse;
+ }
+
+ v2 = edsf_canonify(dsf, v2, &i2);
+ assert(v2 == v1);
+ assert(i2 == inverse);
+
+/* fprintf(stderr, "dsf[%2d] = %2d\n", v2, dsf[v2]); */