How does Kruskal algorithm detect cycle in the graph and what is the time taken ?

Question

Does it tale constant time or the time taken proportional to search in the entire partition of elements to find whether the component lies in that same component or not ?

Answer 1

I think, Kruskal's algorithm can be sure of a cycle when , for an edge (u,v), the condition FindSet(u) == FindSet(v) evaluates to true, which means that both belong to same set.

The time , it would take would be atleast E*log(E) since it has to sort the edges first, before doing anything. In the worst case , the edge causing cycle may be the last edge to be examined in the for loop(see CLRS). Thus in the worst case it is same as running time of algo i.e E*log(V), since |E| < |V|^2.

Answer 2

To detect if two nodes are in same partition, it calls find() function (of disjoint-set data structure) two times. Amortized time complexity of find function is $O(\alpha(V))$, where $\alpha(V)$ is inverse Ackermann function, which we can assume to be constant for all practical purpose. So yes, detecting cycle takes almost constant amount of time.

In the worst case, we have $2*E$ find calls, and hence detecting cycles in whole algorithm is $O(E)$, but since sorting takes $O(E\log E)$ time, overall complexity of algorithm is still $O(E\log E)$.