/category/uf/ /archives/176/ 2017-01-24T19:59:00+08:00 2018.3.3：更新了测试代码，加入了更多写法，修复了一些致命错误 测试机CPU为Intel® Celeron® Processor G3900，内存为8GB DDR4，系统为Debian 9。 编译命令为g++ test.cpp -o test -O3。 先放测试代码： ```c++ #include #include #include #include #define N 1024 #define T 100000 int fa[N+233],st[N+233],sz[N+233]; int find1(int x) { return x==fa[x]?x:fa[x]=find1(fa[x]); } inline int find2(int x) { return x==fa[x]?x:fa[x]=find2(fa[x]); } inline int find3(int x) { while(x!=fa[x])x=fa[x]=fa[fa[x]];return x; } inline int find4(int x) { int se=0;st[0]=x; while(fa[x]!=x)st[++se]=x=fa[x]; while(se)fa[st[--se]]=x; return x; } inline int find5(int x) { int t=x,p; while(x!=fa[x])x=fa[x]; while(t!=x)p=fa[t],fa[t]=x,t=p; return x; } int find6(int x) { return 0>fa[x]?x:fa[x]=find6(fa[x]); } inline int find7(int x) { return 0>fa[x]?x:fa[x]=find7(fa[x]); } inline int find8(int x) { while(fa[x]>=0&&fa[fa[x]]>=0)x=fa[x]=fa[fa[x]];return fa[x]