From afe80030e4935fdebfbed24eeae94274cb7f0632 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Tue, 2 Aug 2005 23:16:46 +0000 Subject: New puzzle: `Slant', picked from the Japanese-language section of nikoli.co.jp (which has quite a few puzzles that they don't seem to have bothered to translate into English). Minor structural change: the disjoint set forest code used in the Net solver has come in handy again, so I've moved it out into its own module dsf.c. [originally from svn r6155] --- dsf.c | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) create mode 100644 dsf.c (limited to 'dsf.c') 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; +} -- cgit v1.1