[sgt/puzzles] / dsf.c

/*
 * 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;
}
Commit	Line	Data
f1010613	1	/*
	2	* dsf.c: two small functions to handle a disjoint set forest,
	3	* which is a data structure useful in any solver which has to
	4	* worry about avoiding closed loops.
	5	*/
	6
	7	int dsf_canonify(int *dsf, int val)
	8	{
	9	int v2 = val;
	10
	11	while (dsf[val] != val)
	12	val = dsf[val];
	13
	14	while (v2 != val) {
	15	int tmp = dsf[v2];
	16	dsf[v2] = val;
	17	v2 = tmp;
	18	}
	19
	20	return val;
	21	}
	22
	23	void dsf_merge(int *dsf, int v1, int v2)
	24	{
	25	v1 = dsf_canonify(dsf, v1);
	26	v2 = dsf_canonify(dsf, v2);
	27	dsf[v2] = v1;
	28	}