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
79. Word Search	Medium
1559. Detect Cycles in 2D Grid	Medium (1837)

General

Problem	Difficulty
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)
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
• 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-like

Problem	Difficulty
1443. Minimum Time to Collect All Apples in a Tree	Medium (1682)
1530. Number of Good Leaf Nodes Pairs	Medium (1745)
1519. Number of Nodes in the Sub-Tree With the Same Label	Medium (1809)

• My contest: https://leetcode.com/problems/minimum-fuel-cost-to-report-to-the-capital/description/ 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
695. Max Area of Island	Medium
@@827. Making A Large Island	Hard (1934)

Path

Problem	Difficulty
1971. Find if Path Exists in Graph	Easy
797. All Paths From Source to Target	Medium (1383)

Bipartite

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)
@@1293. Shortest Path in a Grid with Obstacles Elimination	Hard (1967)
3568. Minimum Moves to Clean the Classroom	Hard
3552. Grid Teleportation Traversal	Medium

Multi-source BFS

Problem	Difficulty
@@994. Rotting Oranges	Medium
542. 01 Matrix	Medium
1162. As Far from Land as Possible	Medium (1666)

To Classify

Problem	Difficulty
684. Redundant Connection	Medium
980. Unique Paths III	Hard

• Solved: https://leetcode.com/problems/restore-the-array-from-adjacent-pairs/description/

Union Find

Problem	Difficulty

TODO: 七、并查集

Explanation

TODO: Add explanation videos