圖論演算法
圖論題描述的是一群東西和它們之間的連結，例如城市與道路，或是「課程表」裡的課程和先修關係。只要看出題目背後的圖，大部分問題都能對應到一個已知的演算法。
九個章節依序是圖的走訪、拓撲排序、最短路徑、最小生成樹、歐拉路徑、強連通與雙連通分量、二分圖染色、網路流，以及其他圖論題。這是整條路線的最後一份題單，前提是你已經能熟練使用遞迴和 BFS。
109 題難度分 1383–30289 章節
進入書房
想要有人陪你寫完這份題單嗎？登入後進入書房，女主角會一次拿一道題目給你。
一、圖的遍歷
§1.1 DFS
| 題目 | 難度分 |
|---|---|
| 547. 省份數量 | 1383 |
| 1971. 尋找圖中是否存在路徑 | 1397 |
| 797. 所有可能的路徑 | 1383 |
| 1306. 跳躍遊戲 III | 1397 |
| 841. 鑰匙和房間 | 1412 |
| 2316. 統計無向圖中無法互相到達點對數 | 1604 |
| 1319. 連通網絡的操作次數 | 1633 |
| 2492. 兩個城市間路徑的最小分數 | 1680 |
| 3310. 移除可疑的方法 | 1711 |
| 2685. 統計完全連通分量的數量 | 1769 |
| 2192. 有向無環圖中一個節點的所有祖先 | 1788 |
| 3387. 兩天自由外匯交易後的最大貨幣數 | 1788 |
| 924. 儘量減少惡意軟件的傳播 | 1869 |
| 2101. 引爆最多的炸彈 | 1880 |
| 721. 賬戶合併 | 未評分 |
| 207. 課程表 | 未評分 |
| 802. 找到最終的安全狀態 | 1962 |
| 3695. 交換元素後的最大交替和 | 1984 |
| 928. 儘量減少惡意軟件的傳播 II | 1985 |
| 2092. 找出知曉秘密的所有專家 | 2004 |
§1.2 BFS
| 題目 | 難度分 |
|---|---|
| 3243. 新增道路查詢後的最短距離 I | 1568 |
| 1311. 獲取你好友已觀看的視頻 | 1653 |
| 3015. 按距離統計房屋對數目 I | 1658 |
| 1129. 顏色交替的最短路徑 | 1780 |
| 2039. 網絡空閒的時刻 | 1865 |
| 2608. 圖中的最短環 | 1904 |
| 815. 公交路線 | 1964 |
§1.3 圖論建模 + BFS Shortest Path
| 題目 | 難度分 |
|---|---|
| 433. 最小基因變化 | 未評分 |
| 1284. 轉化為全零矩陣的最少反轉次數 | 1811 |
| 773. 滑動謎題 | 1815 |
| 752. 打開轉盤鎖 | 1878 |
| 301. 刪除無效的括號 | 未評分 |
| 514. 自由之路 | 未評分 |
| 847. 訪問所有節點的最短路徑 | 2201 |
| 854. 相似度為 K 的字符串 | 2377 |
| 127. 單詞接龍 | 未評分 |
| 488. 祖瑪遊戲 | 未評分 |
二、Topological Sort
§2.1 Topological Sort
| 題目 | 難度分 |
|---|---|
| 210. 課程表 II | 未評分 |
| 2115. 從給定原材料中找到所有可以做出的菜 | 1679 |
| 2392. 給定條件下構造矩陣 | 1961 |
| 802. 找到最終的安全狀態 | 1962 |
| 1591. 奇怪的打印機 II | 2291 |
| 1203. 項目管理 | 2419 |
| 2603. 收集樹中金幣 | 2712 |
§2.2 在Topological Order上 DP
| 題目 | 難度分 |
|---|---|
| 851. 喧鬧和富有 | 1783 |
| 2050. 並行課程 III | 2084 |
| 1857. 有向圖中最大顏色值 | 2313 |
§2.3 Pseudotree
| 題目 | 難度分 |
|---|---|
| 2359. 找到離給定兩個節點最近的節點 | 1715 |
| 2360. 圖中的最長環 | 1897 |
| 684. 冗餘連接 | 未評分 |
| 685. 冗餘連接 II | 未評分 |
| 2876. 有向圖訪問計數 | 2210 |
| 2127. 參加會議的最多員工數 | 2449 |
| 2836. 在傳球遊戲中最大化函數值 | 2769 |
三、Shortest Path
§3.1 Single-Source Shortest Path：Dijkstra Algorithm
§3.2 All-Pairs Shortest Path：Floyd-Warshall Algorithm
| 題目 | 難度分 |
|---|---|
| 2642. 設計可以求最短路徑的圖類 | 1811 |
| 1334. 閾值距離內鄰居最少的城市 | 1855 |
| 2976. 轉換字符串的最小成本 I | 1882 |
| 2959. 關閉分部的可行集合數目 | 2077 |
| 2977. 轉換字符串的最小成本 II | 2696 |
四、Minimum Spanning Tree
四、Minimum Spanning Tree
| 題目 | 難度分 |
|---|---|
| 1584. 連接所有點的最小費用 | 1858 |
| 1489. 找到最小生成樹裡的關鍵邊和偽關鍵邊 | 2572 |
五、Eulerian Path/Eulerian Circuit
五、Eulerian Path/Eulerian Circuit
| 題目 | 難度分 |
|---|---|
| 332. 重新安排行程 | 未評分 |
| 753. 破解保險箱 | 2274 |
| 2097. 合法重新排列數對 | 2651 |
六、Strongly Connected Components (SCC)/Biconnected Components
六、Strongly Connected Components (SCC)/Biconnected Components
| 題目 | 難度分 |
|---|---|
| 1192. 查找集群內的關鍵連接 | 2085 |
| 1568. 使陸地分離的最少天數 | 2209 |
七、Bipartite Coloring
七、Bipartite Coloring
| 題目 | 難度分 |
|---|---|
| 785. 判斷二分圖 | 1625 |
| 886. 可能的二分法 | 1795 |
八、Network Flow
八、Network Flow
| 題目 | 難度分 |
|---|---|
| 1947. 最大兼容性評分和 | 1704 |
| 3376. 破解鎖的最少時間 I | 1793 |
| 2850. 將石頭分散到網格圖的最少移動次數 | 2001 |
| 1879. 兩個數組最小的異或值之和 | 2145 |
| 1349. 參加考試的最大學生數 | 2386 |
| 2172. 數組的最大與和 | 2392 |
| 3276. 選擇矩陣中單元格的最大得分 | 2403 |
| 1595. 連通兩組點的最小成本 | 2538 |
| 3257. 放三個車的價值之和最大 II | 2553 |
九、其他
九、其他
| 題目 | 難度分 |
|---|---|
| 1042. 不鄰接植花 | 1712 |
| 1761. 一個圖中連通三元組的最小度數 | 2005 |
| 2508. 添加邊使所有節點度數都為偶數 | 2060 |
| 1579. 保證圖可完全遍歷 | 2132 |
| 2065. 最大化一張圖中的路徑價值 | 2178 |
| 1697. 檢查邊長度限制的路徑是否存在 | 2300 |
| 2242. 節點序列的最大得分 | 2304 |
| 2493. 將節點分成儘可能多的組 | 2415 |
| 1782. 統計點對的數目 | 2457 |
| 3666. 使二進制字符串全為 1 的最少操作次數 | 2477 |
| 2612. 最少翻轉操作數 | 2824 |
| 3435. 最短公共超序列的字母出現頻率 | 3028 |
| 466. 統計重複個數 | 未評分 |
這是路線上的最後一份題單；核心小節寫完後，女主角會帶你進入進階題單，前面題單的選做小節都在那裡等你。
難度分數來自 zerotrac 的 LeetCode 競賽評分。部分題目沒有 zerotrac 分數，會標示為「未評分」。
進入書房