Expert · Module 28
Advanced Graphs, String Matching & Computational Geometry
Tarjan's SCCs, bridges and articulation points, Dinic's max-flow/min-cut, Z-algorithm and Aho-Corasick automata, and 2D convex hull & sweep-line geometry.
Expert competitive programming and senior systems interviews test specialized structures where naive graph, string, or floating-point approaches fail. This module covers DFS low-link connectivity, max-flow/min-cut duality, linear-time string automata, and integer-exact computational geometry.
- 1Tarjan's Strongly Connected Components (SCC), Bridges, and Articulation PointsPro — members onlyFind all Strongly Connected Components in a directed graph and all critical bridges and cut vertices in an undirected graph in a single O(V + E) DFS pass using discovery times (tin) and low-link values (low).18 min
- 2Network Flow, Min-Cut, and Dinic's Algorithm (Bipartite Matching)Pro — members onlyModel capacity constraints, minimum cuts, and bipartite matching with Residual Graphs, understand why backward edges undo suboptimal greedy choices, and implement Dinic's BFS Level Graph + DFS Pointer-Advancing Blocking Flow.18 min
- 3Linear-Time String Matching: Z-Algorithm, Manacher's, and Aho-CorasickPro — members onlyCompute longest common prefixes for every suffix in O(N) time using the Z-Algorithm's [L, R] Z-box invariant, find all palindromic substrings in O(N) with Manacher's mirror box, and match dictionaries with Aho-Corasick.18 min
- 4Computational Geometry: 2D Cross Products, Convex Hull, and Sweep-LinePro — members onlyReplace error-prone floating-point angles and slopes with exact 64-bit integer 2D Cross Products (CCW orientation), build the Convex Hull in O(N log N) using Andrew's Monotone Chain, and detect intersections with Sweep-Line.18 min