1.1 --- a/lemon/unionfind.h	Thu Nov 13 16:17:50 2008 +0000
     1.2 +++ b/lemon/unionfind.h	Sat Dec 20 22:45:48 2008 +0000
     1.3 @@ -1177,10 +1177,10 @@
     1.4  	    int pd = nodes[jd].parent;
     1.5  	    if (nodes[nodes[jd].next].size < cmax) {
     1.6  	      pushLeft(nodes[jd].next, nodes[jd].left);
     1.7 -	      if (less(nodes[jd].left, nodes[jd].next)) {
     1.8 -		nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
     1.9 -		nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
    1.10 -	      } 
    1.11 +              if (nodes[jd].item == nodes[pd].item) {
    1.12 +                nodes[nodes[jd].next].prio = nodes[jd].prio;
    1.13 +                nodes[nodes[jd].next].item = nodes[jd].item;
    1.14 +	      }
    1.15  	      popLeft(pd);
    1.16  	      deleteNode(jd);
    1.17  	      jd = pd;
    1.18 @@ -1188,9 +1188,10 @@
    1.19  	      int ld = nodes[nodes[jd].next].left;
    1.20  	      popLeft(nodes[jd].next);
    1.21  	      pushRight(jd, ld);
    1.22 -	      if (less(ld, nodes[jd].left)) {
    1.23 +              if (less(ld, nodes[jd].left) || 
    1.24 +                  nodes[ld].item == nodes[pd].item) {
    1.25  		nodes[jd].item = nodes[ld].item;
    1.26 -		nodes[jd].prio = nodes[jd].prio;
    1.27 +		nodes[jd].prio = nodes[ld].prio;
    1.28  	      }
    1.29  	      if (nodes[nodes[jd].next].item == nodes[ld].item) {
    1.30  		setPrio(nodes[jd].next);
    1.31 @@ -1219,10 +1220,10 @@
    1.32  	    int pd = nodes[jd].parent;
    1.33  	    if (nodes[nodes[jd].prev].size < cmax) {
    1.34  	      pushRight(nodes[jd].prev, nodes[jd].right);
    1.35 -	      if (less(nodes[jd].right, nodes[jd].prev)) {
    1.36 -		nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
    1.37 -		nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
    1.38 -	      } 
    1.39 +              if (nodes[jd].item == nodes[pd].item) {
    1.40 +                nodes[nodes[jd].prev].prio = nodes[jd].prio;
    1.41 +                nodes[nodes[jd].prev].item = nodes[jd].item;
    1.42 +	      }
    1.43  	      popRight(pd);
    1.44  	      deleteNode(jd);
    1.45  	      jd = pd;
    1.46 @@ -1230,9 +1231,10 @@
    1.47  	      int ld = nodes[nodes[jd].prev].right;
    1.48  	      popRight(nodes[jd].prev);
    1.49  	      pushLeft(jd, ld);
    1.50 -	      if (less(ld, nodes[jd].right)) {
    1.51 +              if (less(ld, nodes[jd].right) ||
    1.52 +                  nodes[ld].item == nodes[pd].item) {
    1.53  		nodes[jd].item = nodes[ld].item;
    1.54 -		nodes[jd].prio = nodes[jd].prio;
    1.55 +		nodes[jd].prio = nodes[ld].prio;
    1.56  	      }
    1.57  	      if (nodes[nodes[jd].prev].item == nodes[ld].item) {
    1.58  		setPrio(nodes[jd].prev);
    1.59 @@ -1400,7 +1402,14 @@
    1.60                }
    1.61                push(new_id, right_id);
    1.62                pushRight(new_id, ~(classes[r].parent));
    1.63 -              setPrio(new_id);
    1.64 +
    1.65 +              if (less(~classes[r].parent, right_id)) {
    1.66 +                nodes[new_id].item = nodes[~classes[r].parent].item;
    1.67 +                nodes[new_id].prio = nodes[~classes[r].parent].prio;
    1.68 +              } else {
    1.69 +                nodes[new_id].item = nodes[right_id].item;
    1.70 +                nodes[new_id].prio = nodes[right_id].prio;
    1.71 +              }
    1.72  
    1.73                id = nodes[id].parent;
    1.74                classes[r].parent = ~new_id;
    1.75 @@ -1440,7 +1449,14 @@
    1.76                }
    1.77                push(new_id, left_id);
    1.78                pushLeft(new_id, ~(classes[l].parent));
    1.79 -              setPrio(new_id);
    1.80 +
    1.81 +              if (less(~classes[l].parent, left_id)) {
    1.82 +                nodes[new_id].item = nodes[~classes[l].parent].item;
    1.83 +                nodes[new_id].prio = nodes[~classes[l].parent].prio;
    1.84 +              } else {
    1.85 +                nodes[new_id].item = nodes[left_id].item;
    1.86 +                nodes[new_id].prio = nodes[left_id].prio;
    1.87 +              }
    1.88  
    1.89                id = nodes[id].parent;
    1.90                classes[l].parent = ~new_id;