Cycle Detection

Given a million pairwise 'these two accounts belong to the same person' relations, decide whether two arbitrary accounts are now equivalent. Brute-force flood fills are `O(n)` per query; sorting is the wrong shape entirely. **Union-Find** answers each query in nearly `O(1)` amortized time after the relations are merged, with two primitives and a parent array. This lesson covers the disjoint-set abstraction, the `find` operation that walks parent pointers up to a representative, the `union` operation that links two representatives, and the two optimizations (path compression during `find` and union by rank during `union`) that together push the amortized cost to `O(alpha(n))`, where `alpha` is the inverse Ackermann function (effectively constant for any input you can fit in memory). You will trace the parent array as merges happen, and apply the structure to cycle detection in undirected graphs, connected components, equivalence classes, and Kruskal's minimum spanning tree. In **Arrays & Strings**, you saw that an array can encode a mapping from index to value in `O(1)`; a parent array is exactly that mapping, applied to representative pointers. **Graphs: Representation Basics** gave you the vertex-and-edge vocabulary that Union-Find uses to define connectivity, even though the structure itself stores no edges directly. With Union-Find in your toolkit, the curriculum continues with composite designs that combine multiple primitives, starting with the LRU cache pattern.

Webpack figures out the order to compile your modules using topological sort. Google Maps figures out the route to your destination using Dijkstra. Your CI system rejects circular imports using cycle detection. The same handful of graph algorithms power an enormous slice of real infrastructure, and almost all of them are short additions to a BFS or DFS skeleton you already wrote. **Graph Algorithms (Core)** covers that handful in detail. You will implement topological sort in two ways (Kahn's BFS-with-in-degree algorithm and the DFS-reverse-postorder algorithm), cycle detection on undirected graphs (DFS with parent tracking) and on directed graphs (DFS with white/gray/black coloring), Dijkstra's shortest-path algorithm with a min-heap and the relaxation invariant that makes it work, connected-component counting via DFS or Union-Find, and bipartite checking via two-color BFS. Along the way you will see why Dijkstra fails on negative edge weights, which motivates Bellman-Ford in the advanced lesson later. In **BFS & DFS (Intro)**, you wrote the two traversal skeletons. **Weighted Graph Representation** gave you the adjacency-list-of-tuples format that Dijkstra and friends actually consume. This lesson is where those primitives turn into named algorithms with clear use cases. From here, **Greedy (Intro)** introduces a different paradigm: instead of exploring every option, commit to the locally best choice at each step.

Reversing a singly linked list is a four-line iteration with three pointers (`prev`, `curr`, `next`), and yet roughly a third of candidates implement it incorrectly under interview pressure. The reason is that linked-list problems give you no random access: every operation has to be expressed as careful, ordered pointer rewrites, and one missed assignment loses the rest of the list forever. **Linked List Algorithms** is the lesson where pointer manipulation becomes a reliable skill. You will reverse a list iteratively and recursively, then extend the technique to reverse in groups of `k`. You will use Floyd's fast and slow pointers to detect cycles, find the cycle start, locate the middle element, and check whether a list is a palindrome. You will merge two sorted lists, then merge `k` sorted lists with a min-heap. The lesson also covers removing the nth node from the end, finding the intersection of two lists, deep-copying a list with random pointers, and the dummy-node trick that eliminates head-edge cases entirely. In **Linked Lists (Singly)**, you saw how nodes and `next` pointers form a list and why insertion at a known position is `O(1)`. **Two Pointers (Intro)** introduced fast and slow indices on arrays; this lesson reuses the same idea on pointer-linked nodes. Next, **Tree Algorithms** generalizes pointer-and-recursion thinking to branching structures.