Chinaunix首页 | 论坛 | 博客

做不一样的码农dboyaoao.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

DBOYaoao

  • 博客访问： 1062245
  • 博文数量： 77
  • 博客积分： 821
  • 博客等级： 军士长
  • 技术积分： 1905
  • 用 户 组： 普通用户
  • 注册时间： 2011-10-23 16:17
个人简介

学校：上海交通大学软件工程 学历：硕士 行业：从事流媒体移动开发 QQ: 412595942 邮箱：yiikai1987910@gmail.com

文章分类

全部博文（77）

文章存档

2016年（4）

2015年（15）

2014年（16）

2013年（12）

2012年（21）

2011年（9）

我的朋友
最近访客
推荐博文
相关博文
今天开始学算法系列 -- 并查集

分类： C/C++

2015-02-25 13:21:19

     并查集的原理可以google 很多，比较简单。这里主要记录下自己的实现。
     一个典型的应用是在kruskal算法中
    直接上代码：
    

点击(此处)折叠或打开

  1. #define MAXN 7
  2. int ID[MAXN] = { 0 };
  3. int rank[MAXN];
  4. class union_find
  5. {
  6. public:
  7.     union_find();
  8.     int find_root(int x);
  9.     void connect(int x, int y);
  10.     bool isConnected(int x, int y);
  11. };

  13. bool union_find::isConnected(int x, int y)
  14. {
  15.     int xRoot = find_root(x);
  16.     int yRoot = find_root(y);
  17.     if (xRoot == yRoot)
  18.     {
  19.         printf("Has Connected\n");
  20.         return true;
  21.     }
  22.     else
  23.         return false;
  24. }


  27. union_find::union_find()
  28. {
  29.     for (int i = 0; i < MAXN; i++)
  30.     {
  31.         ID[i] = i;
  32.         rank[i] = 1;
  33.     }
  34. }

  36. int union_find::find_root(int x)
  37. {
  38.     if (ID[x] == x)
  39.         return x;
  40.     return find_root(ID[x]);
  41. }

  43. void union_find::connect(int x, int y)
  44. {
  45.     int xRoot = find_root(x);
  46.     int yRoot = find_root(y);
  47.     if (xRoot == yRoot)
  48.     {
  49.         printf("Has Connected\n");
  50.         return;
  51.     }
  52.     if (rank[xRoot] >= rank[yRoot])
  53.     {
  54.         rank[xRoot] += 1;
  55.         ID[yRoot] = ID[xRoot];
  56.     }
  57.     else
  58.     {
  59.         rank[yRoot] += 1;
  60.         ID[xRoot] = ID[yRoot];
  61.     }
  62. }


  65. int _tmain(int argc, _TCHAR* argv[])
  66. {
  67.     union_find m;
  68.     m.connect(ID[0], ID[1]);
  69.     m.connect(ID[2], ID[1]);
  70.     m.connect(ID[3], ID[4]);
  71.     if (m.isConnected(ID[3], ID[4]))
  72.     {
  73.         printf("connected\n");
  74.     }
  75.     return 0;
  76. }

阅读(1659) | 评论(0) | 转发(0) |
0

上一篇：今天开始学算法系列 -- prim

下一篇：今天开始学算法系列 -- kruskal

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6