Graph Algorithms, Dependency Resolution And Connectivity

What's being tested

These problems test graph modeling: converting prerequisites, build dependencies, grids, or flights into nodes and edges with the right direction and constraints. Interviewers are probing whether you can choose between topological sort, DFS cycle detection, Union-Find, and bounded shortest path instead of forcing one graph template everywhere.

Patterns & templates

• Topological sort with indegree + queue — O(V + E) time; if processed count < V, a directed cycle blocks completion.

• DFS cycle detection using visiting / visited states — O(V + E); back-edge to visiting means a dependency cycle exists.

• Build order dependency direction matters — for prerequisite a -> b, decrement indegree[b] only after a is emitted.

• Union-Find / DSU for connectivity — find, union, path compression, union by rank; near-constant amortized time, $O(\alpha(n))$.

• Grid-to-graph mapping — convert (r, c) to id = r * cols + c; union only valid land neighbors to count islands.

• Cheapest flight with K stops — use Bellman-Ford-style relaxation for K + 1 edges, or priority queue with (cost, node, stops) state.

• State includes constraints — shortest path with stop limits is not plain Dijkstra; reaching a city cheaper but with more stops may be unusable.

Common pitfalls

Pitfall: Treating undirected connectivity logic as valid for directed dependency graphs; cycles and reachability have different meanings by edge direction.

Pitfall: Mutating the same distance array during bounded flight relaxation; use a copy per layer to avoid using too many edges.

Pitfall: Returning a partial build order without explicitly checking whether all nodes were processed.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.