Question 86
What is the time complexity of detecting a cycle in an undirected graph using DSU, including initialization of the sets?
Initializing one DSU set per vertex takes O(V), and processing E edges takes O(E $\alpha (V)$) with path compression and union by rank/size. The total is O(V + E $\alpha (V)$). For each edge, compare the representatives of its endpoints; equal representatives indicate a cycle (for a simple undirected graph). Including DSU initialization, a precise bound is O(V+E$\alpha (V)); edge processing alone$ is O(E$\alpha (V)$).