ArcTan

dfs
随笔 - 16, 文章 - 117, 评论 - 6, 引用 - 0
数据加载中……

并查集基础和的应用

今天给SDUT的ACMer看了看并查集,总结总结下:
   并查集,干的就是“并”和“查”两件事。很多与集合相关的操作都可以用并查集高效的解决。

       int Find(int x)
       {
          if (tree[x].parent != x)
          {
              tree[x].parent = Find(tree[x].parent);
          }
          return tree[x].parent;
       }

       void Merge(int a, int b, int p, int q, int d)
       {
          if (tree[q].depth > tree[p].depth) tree[p].parent = q;
          else
          {
              tree[q].parent = p;
              if (tree[p].depth == tree[q].depth) tree[p].depth++;
          }
       }


       其中Find()函数用了路径压缩优化,而Merge()函数用了启发式合并的优化(个人感觉有了路径压缩,启发式合并优化的效果并不明显,而经常因为题目和代码的限制,启发式合并会被我们省略)。

      有个问题,如何求节点到跟节点的距离?

 

posted on 2012-07-26 19:28 wangs 阅读(186) 评论(0)  编辑 收藏 引用 所属分类: ACM-数据结构


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理