Changeset - r460:81d40f1c850c
« 457:561be4
497:8b5660 »
462:1cc281 »
461:1229dc »
gravatar
deba@inf.elte.hu
deba@inf.elte.hu
Bug fix in heap unionfind (ticket #197) The previous bugfix set the minimum value in internal nodes wrongly. It corrects the problem.
0 1 0
default
1 file changed with 4 insertions and 7 deletions:
lemon/unionfind.h
4
7
↑ Collapse diff ↑
lemon/unionfind.h
Show white space 6 line context
... ... 
@@ -1177,7 +1177,8 @@
1177 1177 
            int pd = nodes[jd].parent;
1178 1178 
            if (nodes[nodes[jd].next].size < cmax) {
1179 1179 
              pushLeft(nodes[jd].next, nodes[jd].left);
1180 
              if (nodes[jd].item == nodes[pd].item) {
1180 
              if (less(jd, nodes[jd].next) ||
1181 
                  nodes[jd].item == nodes[pd].item) {
1181 1182 
                nodes[nodes[jd].next].prio = nodes[jd].prio;
1182 1183 
                nodes[nodes[jd].next].item = nodes[jd].item;
1183 1184 
              }
... ... 
@@ -1220,7 +1221,8 @@
1220 1221 
            int pd = nodes[jd].parent;
1221 1222 
            if (nodes[nodes[jd].prev].size < cmax) {
1222 1223 
              pushRight(nodes[jd].prev, nodes[jd].right);
1223 
              if (nodes[jd].item == nodes[pd].item) {
1224 
              if (less(jd, nodes[jd].prev) ||
1225 
                  nodes[jd].item == nodes[pd].item) {
1224 1226 
                nodes[nodes[jd].prev].prio = nodes[jd].prio;
1225 1227 
                nodes[nodes[jd].prev].item = nodes[jd].item;
1226 1228 
              }
... ... 
@@ -1253,11 +1255,6 @@
1253 1255 
      return comp(nodes[id].prio, nodes[jd].prio);
1254 1256 
    }
1255 1257 

			




	1256
	
	
		
    bool equal(int id, int jd) const {


			




	1257
	
	
		
      return !less(id, jd) && !less(jd, id);


			




	1258
	
	
		
    }


			




	1259
	
	
		

			




	1260
	
	
		

			




	1261
	1258
	
		
  public:


			




	1262
	1259
	
		

			




	1263
	1260
	
		
    /// \brief Returns true when the given class is alive.


			




        

    






    
    



    


    

     
    
0 comments (0 inline)