Twelve problems that drill the graph toolkit from Lesson 16 — DFS, BFS, topological sort, union-find, and the two weighted-shortest-path staples. Open a problem, try it yourself first, then read how to reach the solution. Each solution here was actually run and tested.
How to practise. For each problem, first name the tool out loud: “grid flood-fill → DFS”, “dependencies → topological sort”, “are these connected → union-find”, “weights → Dijkstra”. Half the battle in a graph round is picking the right tool in the first thirty seconds. Then write it, and dry-run on the example.
The 12 problems
- 1Number of Islands (LeetCode 200)MediumCount connected groups of land in a grid: treat it as a graph and flood-fill each new island.arrow_forward
- 2Course Schedule (LeetCode 207)MediumCan all courses be finished given prerequisites? Peel off zero in-degree nodes; a cycle leaves some behind.arrow_forward
- 3Course Schedule II (LeetCode 210)MediumReturn an order to take all courses given prerequisites: Kahn's removal order is a topological sort.arrow_forward
- 4Number of Connected Components (LeetCode 323)MediumCount the connected pieces of an undirected graph: start at n and subtract one for each successful union.arrow_forward
- 5Redundant Connection (LeetCode 684)MediumA tree got one extra edge; find it. Add edges with union-find: the first one joining connected nodes is it.arrow_forward
- 6Graph Valid Tree (LeetCode 261)MediumDo these edges form a tree on n nodes? Require exactly n−1 edges, then make sure none closes a cycle.arrow_forward
- 7Surrounded Regions (LeetCode 130)MediumCapture every 'O' region not touching the edge: flood-fill from border 'O's to mark survivors, flip the rest.arrow_forward
- 8Pacific Atlantic Water Flow (LeetCode 417)MediumFind cells whose rain reaches both oceans: flood uphill from each ocean's border, then intersect the sets.arrow_forward
- 9Walls and Gates (LeetCode 286)MediumFill each room with its distance to the nearest gate: BFS from every gate at once, first visit is shortest.arrow_forward
- 10Accounts Merge (LeetCode 721)MediumMerge accounts that share any email: union every email with its account's first email, then group by root.arrow_forward
- 11Network Delay Time (LeetCode 743)MediumHow long until a signal from k reaches every node? Dijkstra from k; the answer is the largest distance.arrow_forward
- 12Cheapest Flights Within K Stops (LeetCode 787)MediumCheapest route from src to dst with at most k stops: run k+1 Bellman-Ford rounds, each on a snapshot.arrow_forward