Can I detect a cycle in an undirected graph with n edges in O(n log*(n)) ? ( log*(n) is log star function )

Question

I have the following algorithm for detecting a cycle in an undirected graph with a set E of n edges :

for each unvisited edge (u, v) in E:
{
    if(Find(u) = Find(v)) // u and v belong to the same set already
    {
        print "Cycle Detected";
        break;
    }

    else
    {
        Union(u, v); // put u and v in the same set
    }
}

my question is can I implement the union-find by size and path compression method and then claim that the time complexity of the code is O(n log^*(n)) worst case?

Answer 1

Assuming you have a connected graph, this algorithm will run in O(n log*(n)) time in the worst case. (In fact, it will even run in O(n α(n)), where α(n) is the extremely slow-growing inverse of the Ackermann function.) If you have a very small number of edges, though, this is not generally true. For instance, consider a graph with n^2 vertices and n edges: even initializing the union-find data structure will take O(n^2) time. If this case matters to you, you could use coordinate compression or implement the union-find structure using hash tables so you only have to deal with vertices present in at least one edge. This will run in O(n α(n)) for any graph.