{ If A is the root of the MFSET then A.leaf ptr holds a pointer to the pointer to A in N.mfsets where N = A.

luster leaf.

We an now des ribe the algorithm.

pro edure solve onstraints1(in S: a system of onstraints of the form od(a; b)  od(
; d)).

return either a luster tree T satisfying S if S is onsistent; or false if S is in onsistent.

variables: m is an integer; a; b are symbols; C is a onstraint in S;

H is an undire ted graph; E ; F are edges; P is an MFSET;

N ; M are nodes of T ;
0. begin if S 
ontains any onstraint of the form, \od(a; b)  od(
; 
)" then return false; 1. H := ;;

2. for ea h onstraint C in S with short E and long F do 3. add E and F to H;

4. add C to E.shorts and to F .longs endfor;

| 4.     | add C to E.shorts and to F .longs endfor;                                                    |                                     |
|--------|----------------------------------------------------------------------------------------------|-------------------------------------|
| 5.     | m := the number of variables in S; ontain the root N;                                        |                                     |
| 7.     | N.symbols := the variables in S; h leaf N of T , INITIALIZE MFSETS(N); h edge E = ab in H do |                                     |
| 10.    | if E.shorts is non-empty and FIND(a) 6= FIND(b) then                                         |                                     |
| 11.    | MERGE(FIND(a), FIND(b)) endif endfor                                                         |                                     |
| 12.    | if every edge E = ab in H satises FIND(a) = FIND(b)                                                                                              |                                     |
| 13.    | then return(false) endif urrent leaf N of T do h                                             |                                     |
| 15.    | if N.mfsets has more than one element then h mfset P in N.mfsets do                          |                                     |
| 16.    | for ea                                                                                       | t node M as a new  hild of N in T ; |
| onstru |                                                                                              |                                     |
| 18.    | M.symbols:= P .symbols;                                                                      |                                     |
| 19.    | endfor endif endfor h edge E = ab in H do                                                    |                                     |
| 21.    | if FIND(a) 6= FIND(b) then onstraint C in E.longs do                                         |                                     |
| 22.    | for ea h                                                                                     |                                     |
| 23.    | delete C from S;                                                                             |                                     |

8. repeat for ea h leaf N of T , INITIALIZE MFSETS(N);

9. for ea h edge E = ab in H do 10. if E.shorts is non-empty and FIND(a) 6= FIND(b) then 11. MERGE(FIND(a), FIND(b)) endif endfor 12. if every edge E = ab in H satises FIND(a) = FIND(b)

13. then return(false) endif 14. for ea h urrent leaf N of T do 15. if N.mfsets has more than one element then 16. for ea h mfset P in N.mfsets do 17. 

onstru t node M as a new hild of N in T ;

18. M.symbols:= P .symbols; 19. endfor endif endfor 20. for ea h edge E = ab in H do 21. if FIND(a) 6= FIND(b) then 22. for ea h onstraint C in E.longs do 23. delete C from S;

24. delete C from E.longs; 25. delete C from C.short.shorts endfor 26. delete E from H endif endfor 27. m := m  1; 28. until S is empty; 29. for ea h leaf N of T

30. N.label := 0; 31. if N.symbols has more than one symbol
