关于一般的并查集求根操作的一组对照研究
关于一般的并查集求根操作的一组对照研究
说道并查集，大家一定对于以多叉树状结构为基础的并查集并不陌生，最常见的两种写法如下
1 function getfat(x:longint):longint;
2 begin
3 while x<>c[x] do x:=c[x];
4 exit(x);
5 end;1 function getfat(x:longint):longint;
2 begin
3 if x<>c[x] then exit(getfat(c[x])) else exit(x);
4 end;其实并查集的核心操作就是一个寻根操作。代码都很短，也很不容易写错，原理也很明显——假如两个点已经到了一个块里的话，那么由于在树结构中，则两者必然有个共同的祖先节点——根节点。。。于是我就这样子学会了并查集
直到某一天在网上看到某神犇在Pascal程序中采用了如下写法——
1 function getfat(x:longint):longint;
2 begin
3 if x<>c[x] then c[x]:=getfat(c[x]);
4 exit(c[x]);
5 end;这个里面的程序和之前的第一段程序相当类似，但有着很大的区别——这个里面不单单是用递归的方式找到了根节点，同时又变更着各个中间各级父亲节点的父节点——实际上都变成了树的根节点，也就是说每个getfat操作之后，得到的树在此点所涉及的支链上都已经被撸到了根节点上（HansBug：喂喂喂别想歪了），这样子对于一再的重复操作可以起到减少树的高度的神奇作用。
说了这些，于是来一个小小的实验比对下——
准备：一个并查集程序，实现功能——输入N、M、T，表示原来有N堆，M次操作，T（1表示用循环并查集；2表示用简单递归并查集；3表示用最下面的新方法）；接下来输入M行，每行"z x y"，"1 x y"表示将x和y所在块合并，"2 x y"表示查看x和y在不在一起。就是这样一个简单的问题
程序如下：（本程序中均不开inline优化，同时均在我家的烂电脑上进行测试，速度比较逗——这么告诉你们吧，我曾经不止一次提心吊胆地把我在本机上单组数据就运行了快2秒的程序交上BZOJ，结果一瞬间AC，时间是1000ms多一点，吓尿了）
1 var
2 i,j,k,l,m,n,t:longint;
3 c:array[0..1000000] of longint;
4 function getfat1(x:longint):longint;
5 begin
6 while x<>c[x] do x:=c[x];
7 exit(x);
8 end;
9 function getfat2(x:longint):longint;
10 begin
11 if x<>c[x] then exit(getfat2(c[x])) else exit(x);
12 end;
13 function getfat3(x:longint):longint;
14 begin
15 if x<>c[x] then c[x]:=getfat3(c[x]);
16 exit(c[x]);
17 end;
18 function getfat(x,y:longint):longint;
19 begin
20 case y of
21 1:exit(getfat1(x));
22 2:exit(getfat2(x));
23 3:exit(getfat3(x));
24 end;
25 end;
26 begin
27 readln(n,m,t);
28 for i:=1 to n do c[i]:=i;
29 for i:=1 to m do
30 begin
31 readln(j,k,l);
32 case j of
33 1:c[getfat(k,t)]:=c[getfat(l,t)];
34 2:writeln(c[getfat(k,t)]=c[getfat(l,t)]);
35 end;
36 end;
37 end.于是开始很开心的对拍：
1.N=1000 M=1000000 —— 结果发现，循环实现的并查集居然最好，大约1.2s左右，然后两种递归实现的并查集都差不多少，大约都1.3s左右，呵呵呵呵。。。神奇
2.N=100 M=10000000 ——现在的数据一定更容易产生高大的树，一方面合并增多了，另一方面原始的块数少了，也就意味着块会更加集中。。。
于是结果是——最新的方法明显强大，大约8-10秒，而这个时候循环实现的并查集还是比递归的快，大约12s，而递归的就要至少13s啦.。。
其实——在原来的并查集中每次合并操作(c[getfat(x)]:=getfat(y);)都已经将一棵树的根节点直接连接到了另一棵树的根节点上，两棵树实现了简单合并，但是对于两点是否在同一块内的访问操作时，原来的程序没有减少高度，也就是说对于同一个树的状态访问多少次都是一样要跑那么高，这样子完全可以构造出很高大的一棵树（通过节节合并不难构造出），每次都会爬好高的树，当然慢啦。。。而这个将每次的树直接缩节后，那么高的树就只需要跑一次了，以后直接一下子就升到根节点上啦！！！哥就是这么霸气！！！
总结：事实证明了新方法的强大，在关于树的问题上，对于树结构的不断优化也必将不断提高算法的速度——这是关于树的问题亘古不变的一个定则！！！最重要的是有get了一个新技能，可以更开心的刷题啦哈哈哈哈^_^
（附1：随机数生成器）
1 var
2 i,j,k,l,m,n:longint;
3 a:array[0..10000000,1..3] of longint;
4 begin
5 readln(n,m);
6 randomize;
7 for i:=1 to m do
8 begin
9 a[i,1]:=random(2)+1;
10 a[i,2]:=random(n)+1;
11 a[i,3]:=random(n)+1;
12 end;
13 assign(output,'bxj1.txt');
14 rewrite(output);
15 writeln(n,' ',m,' ',1);
16 for i:=1 to m do writeln(a[i,1],' ',a[i,2],' ',a[i,3]);
17 close(output);
18 assign(output,'bxj2.txt');
19 rewrite(output);
20 writeln(n,' ',m,' ',2);
21 for i:=1 to m do writeln(a[i,1],' ',a[i,2],' ',a[i,3]);
22 close(output);
23 assign(output,'bxj3.txt');
24 rewrite(output);
25 writeln(n,' ',m,' ',3);
26 for i:=1 to m do writeln(a[i,1],' ',a[i,2],' ',a[i,3]);
27 close(output);
28 end.（附2：bat小程序，用于对拍，fuckbxj.exe表示随机数生成器）
1 @echo off
2 set /a s=0
3 :1
4 set /a s=s+1
5 echo Test %s%
6 rem 此处两个数分别表示N和M
7 echo 100 10000000|fuckbxj.exe
8 echo 循环求并查集
9 echo.|time
10 type bxj1.txt|bxj.exe >bxj1.out
11 echo.|time
12 echo 递归求并查集
13 echo.|time
14 type bxj2.txt|bxj.exe >bxj2.out
15 echo.|time
16 echo 优化递归并查集
17 echo.|time
18 type bxj3.txt|bxj.exe >bxj3.out
19 echo.|time
20 fc bxj1.out bxj2.out
21 fc bxj1.out bxj3.out
22 pause
23 goto 1