2018.3.3：更新了测试代码，加入了更多写法，修复了一些致命错误
测试机CPU为Intel® Celeron® Processor G3900，内存为8GB DDR4，系统为Debian 9。
编译命令为g++ test.cpp -o test -O3。
先放测试代码：

  1. #include<cstdio>
  2. #include<ctime>
  3. #include<random>
  4. #include<cassert>
  5. #define N 1024
  6. #define T 100000
  7. int fa[N+233],st[N+233],sz[N+233];
  8. int find1(int x)
  9. {
  10.     return x==fa[x]?x:fa[x]=find1(fa[x]);
  11. }
  12. inline int find2(int x)
  13. {
  14.     return x==fa[x]?x:fa[x]=find2(fa[x]);
  15. }
  16. inline int find3(int x)
  17. {
  18.     while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;
  19. }
  20. inline int find4(int x)
  21. {
  22.     int se=0;st[0]=x;
  23.     while(fa[x]!=x)st[++se]=x=fa[x];
  24.     while(se)fa[st[--se]]=x;
  25.     return x;
  26. }
  27. inline int find5(int x)
  28. {
  29.     int t=x,p;
  30.     while(x!=fa[x])x=fa[x];
  31.     while(t!=x)p=fa[t],fa[t]=x,t=p;
  32.     return x;
  33. }
  34. int find6(int x)
  35. {
  36.     return 0>fa[x]?x:fa[x]=find6(fa[x]);
  37. }
  38. inline int find7(int x)
  39. {
  40.     return 0>fa[x]?x:fa[x]=find7(fa[x]);
  41. }
  42. inline int find8(int x)
  43. {
  44.     while(fa[x]>=0&&fa[fa[x]]>=0)x=fa[x]=fa[fa[x]];return fa[x]<0?x:fa[x];
  45. }
  46. long long global_checksum;
  47. unsigned int count,seed;
  48. std::mt19937 ran_(0);
  49. void init_rand(int x)
  50. {
  51.     ran_=std::mt19937(x);
  52.     ran_(),ran_(),ran_();
  53.     count=0;
  54. }
  55. int rand()
  56. {
  57.     if(count&1023)seed=ran_();
  58.     count++;
  59.     seed^=seed<<13;
  60.     seed^=seed>>17;
  61.     seed^=seed<<5;
  62.     return seed;
  63. }
  64. inline long long test(int(*f)(int))
  65. {
  66.     init_rand(19260817);
  67.     long long last,timeusage=0,checksum=0;
  68.     for(int t=0;t<T;t++)
  69.     {
  70.         for(int i=0;i<N;i++)fa[i]=i;
  71.         last=clock();
  72.         for(int i=0,x,y;i<N;i++)
  73.         {
  74.             x=rand(),y=rand();
  75.             x&=N-1,y&=N-1;
  76.             x=f(x),y=f(y);
  77.             if(x!=y)fa[x]=y;
  78.         }
  79.         timeusage+=clock()-last;
  80.         for(int i=0;i<N;i++)checksum=checksum*998244353+(f(i)==f(0));
  81.     }
  82.     assert(global_checksum==checksum||global_checksum==0);
  83.     global_checksum=checksum;
  84.     return timeusage;
  85. }
  86. inline long long test2(int(*f)(int))
  87. {
  88.     init_rand(19260817);
  89.     long long last,timeusage=0,checksum=0;
  90.     for(int t=0;t<T;t++)
  91.     {
  92.         for(int i=0;i<N;i++)fa[i]=i;
  93.         for(int i=0;i<N;i++)sz[i]=1;
  94.         last=clock();
  95.         for(int i=0,x,y;i<N;i++)
  96.         {
  97.             x=rand(),y=rand();
  98.             x&=N-1,y&=N-1;
  99.             x=f(x),y=f(y);
  100.             if(x!=y){if(sz[x]>sz[y])sz[x]+=sz[y],fa[y]=x;else sz[y]+=sz[x],fa[x]=y;}
  101.         }
  102.         timeusage+=clock()-last;
  103.         for(int i=0;i<N;i++)checksum=checksum*998244353+(f(i)==f(0));
  104.     }
  105.     assert(global_checksum==checksum||global_checksum==0);
  106.     global_checksum=checksum;
  107.     return timeusage;
  108. }
  109. inline long long test3(int(*f)(int))
  110. {
  111.     init_rand(19260817);
  112.     long long last,timeusage=0,checksum=0;
  113.     for(int t=0;t<T;t++)
  114.     {
  115.         for(int i=0;i<N;i++)fa[i]=-1;
  116.         last=clock();
  117.         for(int i=0,x,y;i<N;i++)
  118.         {
  119.             x=rand(),y=rand();
  120.             x&=N-1,y&=N-1;
  121.             x=f(x),y=f(y);
  122.             if(x!=y){if(fa[x]<fa[y])fa[x]+=fa[y],fa[y]=x;else fa[y]+=fa[x],fa[x]=y;}
  123.         }
  124.         timeusage+=clock()-last;
  125.         for(int i=0;i<N;i++)checksum=checksum*998244353+(f(i)==f(0));
  126.     }
  127.     assert(global_checksum==checksum||global_checksum==0);
  128.     global_checksum=checksum;
  129.     return timeusage;
  130. }
  131. inline long long test2_1(int(*f)(int))
  132. {
  133.     init_rand(19260817);
  134.     long long last,timeusage=0,checksum=0;
  135.     for(int t=0;t<T;t++)
  136.     {
  137.         for(int i=0;i<N;i++)fa[i]=i;
  138.         for(int i=0;i<N;i++)sz[i]=1;
  139.         last=clock();
  140.         for(int i=0,x,y;i<N;i++)
  141.         {
  142.             x=rand(),y=rand();
  143.             x&=N-1,y&=N-1;
  144.             x=f(x),y=f(y);
  145.             if(x!=y){if(sz[x]>sz[y])fa[y]=x;else{fa[x]=y;if(sz[x]==sz[y])sz[y]++;}}
  146.         }
  147.         timeusage+=clock()-last;
  148.         for(int i=0;i<N;i++)checksum=checksum*998244353+(f(i)==f(0));
  149.     }
  150.     assert(global_checksum==checksum||global_checksum==0);
  151.     global_checksum=checksum;
  152.     return timeusage;
  153. }
  154. inline long long test3_1(int(*f)(int))
  155. {
  156.     init_rand(19260817);
  157.     long long last,timeusage=0,checksum=0;
  158.     for(int t=0;t<T;t++)
  159.     {
  160.         for(int i=0;i<N;i++)fa[i]=-1;
  161.         last=clock();
  162.         for(int i=0,x,y;i<N;i++)
  163.         {
  164.             x=rand(),y=rand();
  165.             x&=N-1,y&=N-1;
  166.             x=f(x),y=f(y);
  167.             if(x!=y){if(fa[x]<fa[y])fa[y]=x;else{if(fa[x]==fa[y])fa[y]--;fa[x]=y;}}
  168.         }
  169.         timeusage+=clock()-last;
  170.         for(int i=0;i<N;i++)checksum=checksum*998244353+(f(i)==f(0));
  171.     }
  172.     assert(global_checksum==checksum||global_checksum==0);
  173.     global_checksum=checksum;
  174.     return timeusage;
  175. }
  176. int main()
  177. {
  178.     printf("CLOCKS_PER_SEC:%d\n",CLOCKS_PER_SEC);
  179.     printf("find1:%lld %lld %lld\n",test(find1),test2(find1),test2_1(find1));
  180.     printf("find2:%lld %lld %lld\n",test(find2),test2(find2),test2_1(find2));
  181.     printf("find3:%lld %lld %lld\n",test(find3),test2(find3),test2_1(find3));
  182.     printf("find4:%lld %lld %lld\n",test(find4),test2(find4),test2_1(find4));
  183.     printf("find5:%lld %lld %lld\n",test(find5),test2(find5),test2_1(find5));
  184.     printf("find6:%lld %lld\n",test3(find6),test3_1(find6));
  185.     printf("find7:%lld %lld\n",test3(find7),test3_1(find7));
  186.     printf("find8:%lld %lld\n",test3(find8),test3_1(find8));
  187. }

当N=1024,T=500000时，输出：

  1. find1:20089351 15887467 16531550
  2. find2:20097390 15910071 16540963
  3. find3:17256541 13390076 13982165
  4. find4:19644034 15645215 16138683
  5. find5:19427605 15368866 15878426
  6. find6:15846219 16573551
  7. find7:15818575 16527184
  8. find8:14988614 15839679

当N=131072,T=5000时，输出：

  1. CLOCKS_PER_SEC:1000000
  2. find1:40043295 28478678 29630797
  3. find2:40079319 28487803 29605407
  4. find3:34651392 23403124 24607184
  5. find4:40438077 27544080 28666981
  6. find5:39498635 26400323 27404284
  7. find6:25862629 26859295
  8. find7:25814962 26853594
  9. find8:24541376 25698358

当N=2097152,T=500时，输出：

  1. CLOCKS_PER_SEC:1000000
  2. find1:240728970 173155213 166865669
  3. find2:240076225 173137194 166896002
  4. find3:257240885 186958166 159086582
  5. find4:240671337 168750996 164743633
  6. find5:210863641 130934764 128655852
  7. find6:107561256 107685991
  8. find7:107630995 107676199
  9. find8:101390000 100197421

当N=16777216,T=400时，输出：

  1. CLOCKS_PER_SEC:1000000
  2. find1:2537867344 1538207603 1438028041
  3. find2:2542492294 1537816024 1438141065
  4. find3:2878818361 1750536054 1388536804
  5. find4:2497444413 1495104276 1413699601
  6. find5:2212506256 1083761103 1015381467
  7. find6:983906431 926941775
  8. find7:984064763 926552621
  9. find8:892107319 808279658

（原结果有误，已删）
最后得出的结果是find8（while非递归+按秩合并+秩和fa记在一个数组上）最快，当N较小时秩选用size，当N较大时秩选用depth。
当不方便非递归时可以写递归的（find6或find7）。
inline似乎没有明显优化。