1 files changed, 28 insertions, 0 deletions
diff --git a/dsf.c b/dsf.c
new file mode 100644
index 0000000..353bf1a
--- /dev/null
+++ b/dsf.c
@@ -0,0 +1,28 @@
+/*
+ * dsf.c: two small functions to handle a disjoint set forest,
+ * which is a data structure useful in any solver which has to
+ * worry about avoiding closed loops.
+ */
+
+int dsf_canonify(int *dsf, int val)
+{
+    int v2 = val;
+
+    while (dsf[val] != val)
+	val = dsf[val];
+
+    while (v2 != val) {
+	int tmp = dsf[v2];
+	dsf[v2] = val;
+	v2 = tmp;
+    }
+
+    return val;
+}
+
+void dsf_merge(int *dsf, int v1, int v2)
+{
+    v1 = dsf_canonify(dsf, v1);
+    v2 = dsf_canonify(dsf, v2);
+    dsf[v2] = v1;
+}