n边无向图环检测用优化并查集 时间复杂度是否为O(n log*(n))

• 可以在O(n logn)（logn为对数星函数）时间复杂度下，完成n条边规模无向图的环检测，你给出的基于并查集的算法逻辑是正确的。

对应算法实现逻辑如下：

for each unvisited edge (u, v) in E:
{
    if(Find(u) = Find(v)) // u和v已属于同一连通集合
    {
        print "Cycle Detected";
        break;
    }
    else
    {
        Union(u, v); // 将u和v合并入同一连通集合
    }
}

双优化并查集的复杂度判定 #

针对你提出的「采用按大小合并+路径压缩实现并查集时，上述代码最坏时间复杂度是否为O(n log*n)」的问题，结论是该复杂度声明完全成立：

• 同时启用按大小（按秩）合并、路径压缩两项优化的并查集，单次Find/Union操作的均摊时间复杂度为O(α(n))，其中α(n)为阿克曼函数的反函数。该函数的增长速度比对数星函数log*n更慢：哪怕n的取值达到宇宙可观测原子总数的量级，α(n)的取值也不会超过5。
• 由于O(α(n))是比O(logn)更严格的复杂度上界，因此遍历n条边的整体最坏时间复杂度O(n α(n))，自然满足O(n logn)的上界要求。

注：不少算法教材和工程文档会直接将双优化并查集的单操作均摊复杂度简化表述为O(log*n)，这是行业内普遍接受的表述方式，不存在事实错误。

内容的提问来源于stack exchange，提问作者MOUSA GANG