Detect cycles in an undirected graph using Disjoint Set Union. Watch each edge get tested: if two nodes already share a root, adding that edge creates a cycle.
DSU can detect cycles in an undirected graph in O(E·α(N)). When adding edge (u, v), if Find(u) == Find(v) they are already connected, so adding this edge would create a cycle.
An undirected edge (u, v) creates a cycle if and only if u and v are already in the same component (same root). This is because there already exists a path between them.
Process each edge. If the two endpoints share a root, report a cycle and stop (or continue marking). Otherwise, call Union to merge their components.
Cycle detection with DSU is used in Kruskal's MST algorithm (skip edges that would create cycles), checking if a graph is a tree (N-1 edges, no cycles), and network validation.
Pick a preset and click Run to test each edge. Green edges are safe; red edges create a cycle. Watch the DSU tree grow until a cycle is detected.