KM算法入门

对于并查集： 很多次都是迷迷糊糊，尤其是对并查集的优化：

1.路径压缩  2.按秩合并

对此个人整理了一下：

对于最基本的并查集建议看看：

百度百科：  http://baike.baidu.com/view/521705.htm

以例题的形式分析，并用算法描述了

博客园：   对于有点基础的可以参考下，清晰明了

http://www.cnblogs.com/cherish_yimi/archive/2009/10/11/1580839.html

对于第二个优化按秩合并的部分处理有点异议：

if(rank[x] < rank[y])
              {
                  num[x]=y;
              
              }
              else if(rank[x]> rank[y])
              {
                  num[y]=x;
              }
              else rank[y]++;

看到很多博客上都是这么写的，就连维基百科上也是这么处理的！

个人感觉这样会大大使按秩合并的优化打折，这样处理应该比上面的哪个要严谨多了

           if(rank[x] <= rank[y])
              {
                  num[x]=y;
                  rank[y]+=rank[x];
              }
              else if(rank[x]> rank[y])
              {
                  num[y]=x;
                  rank[x]+=rank[y];
              }

而在sdutoj 2391测试  时间只是略快