前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法模板——并查集 1

算法模板——并查集 1

作者头像
HansBug
发布2018-04-10 16:40:22
5050
发布2018-04-10 16:40:22
举报
文章被收录于专栏:HansBug's Lab

实现功能——操作1:将两个数字合并到一个集合内;操作2:判断两个数字是否在一起

第6行是亮点,这个优化能快出不少,真的

代码语言:javascript
复制
 1 var
 2    i,j,k,l,m,n:longint;
 3    c:array[0..100000] of longint;
 4 function getfat(x:longint):longint;inline;
 5          begin
 6               if c[x]<>x then c[x]:=getfat(c[x]);   //亮点在这里么么哒
 7               exit(c[x]);
 8          end;
 9 begin
10      readln(n);
11      for i:=1 to n do c[i]:=i;
12      while true do
13            begin
14                 read(i);if (i<1) or (i>2) then halt;
15                 readln(j,k);
16                 case i of
17                      1:c[getfat(j)]:=getfat(k);    //合并
18                      2:if getfat(j)=getfat(k) then writeln('Together!') else writeln('Not together!'); //判断是否已合并
19                 end;
20            end;
21 end.
22              
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015-01-20 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档