Cycle Detection in Undirected Graphs

DSUs can be used to detect a cycle ... we iterate through edges and merge nodes that are in same graph ... once we try to merge an edge where both nodes are already in same graph, we detected a cycle ... O(edges * time to find absolute root (worst case, go through all the verticies)) https://www.youtube.com/watch?v=eTaWFhPXPz4 https://www.hackerearth.com/practice/notes/abhinav92003/disjoint-set-union/#:~:text=Disjoint%20Set%20Union%20(DSU)%20or,may%20have%20multiple%20connected%20components. https://cp-algorithms.com/data_structures/disjoint_set_union.html

Other algos (BFS/DFS) https://stackoverflow.com/questions/862578/fastest-algorithm-for-detecting-a-loop-in-a-graph