# HG changeset patch
# User deba
# Date 1229890408 0
# Node ID 511cf2518a32a988d226108a235afa802851499a
# Parent  212ea31bf6b93f3af3d86a91ebe2aa9eb3a7d462
Backport hg commit [81d40f1c850c] (ticket #197)

diff -r 212ea31bf6b9 -r 511cf2518a32 lemon/unionfind.h
--- a/lemon/unionfind.h	Sat Dec 20 22:45:48 2008 +0000
+++ b/lemon/unionfind.h	Sun Dec 21 20:13:28 2008 +0000
@@ -1177,7 +1177,8 @@
 	    int pd = nodes[jd].parent;
 	    if (nodes[nodes[jd].next].size < cmax) {
 	      pushLeft(nodes[jd].next, nodes[jd].left);
-              if (nodes[jd].item == nodes[pd].item) {
+              if (less(jd, nodes[jd].next) ||
+		  nodes[jd].item == nodes[pd].item) {
                 nodes[nodes[jd].next].prio = nodes[jd].prio;
                 nodes[nodes[jd].next].item = nodes[jd].item;
 	      }
@@ -1220,7 +1221,8 @@
 	    int pd = nodes[jd].parent;
 	    if (nodes[nodes[jd].prev].size < cmax) {
 	      pushRight(nodes[jd].prev, nodes[jd].right);
-              if (nodes[jd].item == nodes[pd].item) {
+              if (less(jd, nodes[jd].prev) ||
+		  nodes[jd].item == nodes[pd].item) {
                 nodes[nodes[jd].prev].prio = nodes[jd].prio;
                 nodes[nodes[jd].prev].item = nodes[jd].item;
 	      }