graph-problems.md

Graph Problems

Traversal

Grid

Problem	Difficulty
733. Flood Fill	Easy
463. Island Perimeter	Easy
417. Pacific Atlantic Water Flow	Medium
1905. Count Sub Islands	Medium
**1559. Detect Cycles in 2D Grid	Medium (1837)

General

Problem	Difficulty	Notes
841. Keys and Rooms	Medium (1412)
1306. Jump Game III	Medium (1396)
**133. Clone Graph	Medium
399. Evaluate Division	Medium
**2192. All Ancestors of a Node in a Directed Acyclic Graph	Medium (1787)	Very tricky way to build topological sort.
2101. Detonate the Maximum Bombs	Medium (1880)
**721. Accounts Merge	Medium
2092. Find All People With Secret	Medium (2003)

• https://leetcode.com/problems/number-of-provinces/description/
• Solved, https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/description/ 1489
• Solved, https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/description/ 1512
• Solved, https://leetcode.com/problems/restore-the-array-from-adjacent-pairs/description/
• https://leetcode.com/problems/number-of-enclaves/submissions/ 1615
• https://leetcode.com/problems/maximum-number-of-moves-in-a-grid/description/ 1625
• https://leetcode.com/problems/remove-methods-from-project/description/ 1710
• https://leetcode.com/problems/count-the-number-of-complete-components/description/ 1769
• https://leetcode.com/problems/maximize-amount-after-two-days-of-conversions/description/ 1787

Tree in Graph

Problem	Difficulty
1376. Time Needed to Inform All Employees	Medium (1560)
1443. Minimum Time to Collect All Apples in a Tree	Medium (1682)
1519. Number of Nodes in the Sub-Tree With the Same Label	Medium (1809)
**2477. Minimum Fuel Cost to Report to the Capital	Medium (2011)

Connected Components

Problem	Difficulty
200. Number of Islands	Medium
**130. Surrounded Regions	Medium
1254. Number of Closed Islands	Medium (1659)
2316. Count Unreachable Pairs of Nodes in an Undirected Graph	Medium (1604)
1319. Number of Operations to Make Network Connected	Medium (1633)

Area

Problem	Difficulty	Notes
695. Max Area of Island	Medium
**827. Making A Large Island	Hard (1934)	How to record the area of the island? How to connect the islands?

Path

Problem	Difficulty	Notes
1971. Find if Path Exists in Graph	Easy
797. All Paths From Source to Target	Medium (1383)
**79. Word Search	Medium	Path finding, need backtracking.
980. Unique Paths III	Hard

Graph Coloring

Problem	Difficulty
785. Is Graph Bipartite?	Medium
886. Possible Bipartition	Medium
1042. Flower Planting With No Adjacent	Medium (1712)

Topological Sort

Problem	Difficulty
207. Course Schedule	Medium
**210. Course Schedule II	Medium
2115. Find All Possible Recipes from Given Supplies	Medium (1679)
2192. All Ancestors of a Node in a Directed Acyclic Graph	Medium (1787)
310. Minimum Height Trees	Medium

• https://leetcode.com/problems/course-schedule-iv/description/ 1692
• https://leetcode.com/problems/loud-and-rich/description/ 1783
• https://leetcode.com/problems/find-eventual-safe-states/description/ 1962
• https://leetcode.com/problems/build-a-matrix-with-conditions/description/ 1960
• https://leetcode.com/problems/parallel-courses-iii/ 2084

BFS

• https://leetcode.com/problems/shortest-distance-after-road-addition-queries-i/description/ 1567
• https://leetcode.com/problems/get-watched-videos-by-your-friends/description/ 1652
• https://leetcode.com/problems/map-of-highest-peak/description/ 1782, as same as 542. 01 Matrix
• https://leetcode.com/problems/minimum-sideway-jumps/description/ 1778
• https://leetcode.com/problems/shortest-cycle-in-a-graph/description/ 1904
• https://leetcode.com/problems/bus-routes/description/ 1964
• https://leetcode.com/problems/snakes-and-ladders/description/ 2019
• https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/description/ 2068
• https://leetcode.com/problems/cut-off-trees-for-golf-event/description/ h

Single-source BFS

Problem	Difficulty
127. Word Ladder	Hard
1091. Shortest Path in Binary Matrix	Medium
433. Minimum Genetic Mutation	Medium
1926. Nearest Exit from Entrance in Maze	Medium (1638)
1129. Shortest Path with Alternating Colors	Medium (1779)
**934. Shortest Bridge	Medium (1825)
752. Open the Lock	Medium (1877)
3552. Grid Teleportation Traversal	Medium

Multi-Source BFS

Problem	Difficulty	Notes
**994. Rotting Oranges	Medium
**542. 01 Matrix	Medium	Distance matrix, no visited set needed. OR 2-pass DP.
1162. As Far from Land as Possible	Medium (1666)

Multi-State BFS

Problem	Difficulty
**1293. Shortest Path in a Grid with Obstacles Elimination	Hard (1967)
3568. Minimum Moves to Clean the Classroom	Hard

Union Find

Problem	Difficulty
**547. Number of Provinces	Medium
684. Redundant Connection	Medium

TODO: 七、并查集

Explanation

TODO: Add explanation videos