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