Cycle Detection

Using DFS

• Find back edges
  • An edge that connects to an ancestor during DFS traversal
• For every node, keep track of the predecessor node and make sure no edge connects back to the predecessor
• Time complexity: $O(E+V)$

Using Disjoint Sets

• Maintain a different disjoint set for each disconnected section of the graph

When adding edge i->j
if find(i) != find(j)
	union(i, j)

Disjoint Sets (Weighted Union)

• A group of sets
  • There is no item is common in any of the sets
• Operations
  • find(i): identify the set that contains i
  • union(i, j): merge the set that contains i and the set that contains j
• Disjoint sets represent connected components
• A cycle is created by adding an edge for which both vertices are in the same connected component
• Representation
  • An array where each index stores the parent of the “index” vertex
  • An entire set is represented as a tree