专栏首页HansBug's Lab算法模板——并查集 2(支持快速即时查询本连通块内容,纯原创!)

算法模板——并查集 2(支持快速即时查询本连通块内容,纯原创!)

实现功能:输入N,现在有N个数;接下来输入任意行,如果是"1 x y"则表示把x和y所在的块合并;如果是"2 x"则表示输出x所在的块的全部内容

原理:其实主要是自己创造了一个可并链line,he表示链头,ta表示链尾,然后对于不同块之间的合并就是直接把两条链对接,也就是一个的尾巴接到另一个的头上,构成新链(由于是链的直接叠加,所以可以做到严格的O(1),并且输出时输出多少复杂度就是多少,完全不存在额外复杂度)。然后同时用原本的普通数组并查集进行维护和追踪(理论值为O(logn)但实际上由于c[x]:=getfat(c[x])的优化导致实际测试结果远远小于这一复杂度)

复杂度:【合并操作O(1),查询O(块大小)(意味着复杂度几乎完全用来输出)】×N,相比于之前的算法对于即时处理的性能有所提高,但是只需要最终进行静态的全局处理时,两者差不太多,这个会略快些,传统程序代码略少些

(PS:值得注意的是,这种新的数据结构中千万要特判两个数字处于同一块的情况,必须避免同一条链首尾相接导致产生环!!!本程序41行continue那里有所体现。同时c[x]:=y之类的合并块语句以及merge(x,y)操作是有顺序之分的,两者顺序必须保持一致,不想原来的并查集顺序任意)

 1 type
 2     point=^node;
 3     node=record
 4                g:longint;
 5                next:point;
 6     end;
 7     line=record
 8                he,ta:point;
 9     end;
10 var
11    a:array[0..100000] of line;
12    c:array[0..100000] of longint;
13    i,j,k,l,m,n:longint;
14    p:point;
15 procedure merge(var p1,p2:line);inline;
16           begin
17                p1.ta^.next:=p2.he;
18                p1.ta:=p2.ta;
19                p2.he:=nil;p2.ta:=nil;
20           end;
21 function getfat(x:longint):longint;inline;
22          begin
23               if x<>c[x] then c[x]:=getfat(c[x]);
24               exit(c[x]);
25          end;
26 begin
27      readln(n);
28      for i:=1 to n do
29          begin
30               c[i]:=i;
31               new(p);p^.g:=i;p^.next:=nil;
32               a[i].he:=p;a[i].ta:=p;
33          end;
34      while true do
35            begin
36                 read(l);
37                 case l of
38                      1:begin
39                             readln(j,k);
40                             j:=getfat(j);k:=getfat(k);
41                             if j=k then continue;
42                             c[k]:=j;
43                             merge(a[j],a[k]);
44                      end;
45                      2:begin
46                             readln(j);
47                             j:=getfat(j);
48                             p:=a[j].he;
49                             while p<>nil do
50                                   begin
51                                        write(p^.g,' ');
52                                        p:=p^.next;
53                                   end;
54                             writeln;
55                      end;
56                 end;
57 
58            end;
59 end.         

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1131: [POI2008]Sta

    1131: [POI2008]Sta Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 783  Solved:...

    HansBug
  • 2292: 【POJ Challenge 】永远挑战

    2292: 【POJ Challenge 】永远挑战 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 553 ...

    HansBug
  • 1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果

    1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果 Time Limit: 5 Sec  Memory L...

    HansBug
  • Java基础:一、伴随多态的可互换对象(7)

    在处理类型的层次结构时,经常把一个对象不当作它所属的特定类型来对象,而是将其当作其基类的对象类对象。这称为“泛化” ,这样可以编写出不依赖特定类型的代码。

    桑鱼
  • 强化学习(Reinforcement Learning)应用于量化投资系列专题(二)——设计一个外汇交易系统基于自适应强化学习

    往期文章(点击标题查看) 强化学习(Reinforcement Learning)系列(一) 今天带来机器学习应用于量化投资系列之 强化学习(Reinforce...

    量化投资与机器学习微信公众号
  • AI大事件 | 谷歌云把英伟达Tesla GPU的价格降低了36%,苹果发布无人驾驶汽车的最新研究成果

    大数据文摘
  • 学习WPF——元素绑定

    概念 从源对象提取一些信息,并用这些信息设置目标对象的属性 示例 image.png image.png 数据绑定表达式使用XAML的标记扩展(因此具有花括号)...

    liulun
  • 2019-2-13-wcf入门(15)

    绑定是用于配置wcf如何进行endpoint的对象,其包括协议配置(如2019-2-12-wcf入门(14) - huangtengxiao用到的可靠会话配置)...

    黄腾霄
  • 北京蚂蚁三四面

    三面: spring AOP原理,用了什么设计模式 一致性哈希原理 问我用过机器学习没(讲了下本科做过的一个ocr,然后问我以图搜图怎么做) 项目里行为特征树怎...

    牛客网
  • SpringMVC:数据绑定入门(-)

    1.数据类型,可以绑定基本数据类型,如int age,或者包装类型如:Integer age;

    Dar_Alpha

扫码关注云+社区

领取腾讯云代金券