286. Walls and Gates
題目網址：https://leetcode.cn/problems/walls-and-gates/
題意：給一 m × n 的網格 rooms, 其中每個 cell 有三種可能：
1 表示牆 or 障礙物
0 表示門
INF 表示空房間。用 2^31 - 1 = 2147483647 代表 INF。且通往門的距離總是小於 2147483647
返回每個空房間位到最近門的距離。如果無法到達門, 則距離設為 INF。
Solution：
想法：利用 BFS（因為可能不只一個門）, 以門為起點向外做 BFS
typedef pair<int, int> pii;class Solution {public: void wallsAndGates(vector<vector<int>>& rooms) { m = rooms.size(), n = rooms[0].size(); int dist = 1; // 房間離門的最小距離為 1 for (int i = 0 ...
207. Course Schedule
題目網址：https://leetcode.cn/problems/course-schedule/
題意：你這學期必須選修 numCourses 門課程, 標記為 0 到 numCourses - 1。
在修習某些課程前需要一些先修課程 prerequisites, 其中 prerequisites[i] = [a_i, b_i], 表示要修 a_i 前必須先修 b_i。
e.g. [0, 1] 表示想要修課程 0, 需要先完成課程 1。
返回是否能完成所有課程。
Solution 1：
想法：利用 Topological Sort + BFS, 依序取出 inDegree = 0 之 node
在 BFS 中, [0, 1] 表示想要修課程 0, 需要先完成課程 1。用圖表示為 1 指向 0（方向跟 DFS 相反）, 這樣 1 的 inDegree = 0, 才會優先被執行
首先將 inDegree = 0 的 node（不需要任何先修課程的課）加入到 queue 中
BFS
取出 queue.front() 後, 將其相鄰 node 的 inDegree - 1
若 ...
210. Course Schedule II
題目網址：https://leetcode.cn/problems/course-schedule-ii/
題意：你這學期必須選修 numCourses 門課程, 標記為 0 到 numCourses - 1。
在修習某些課程前需要一些先修課程 prerequisites, 其中 prerequisites[i] = [a_i, b_i], 表示要修 a_i 前必須先修 b_i。
e.g. [0, 1] 表示想要修課程 0, 需要先完成課程 1。
返回能夠學習完所有可成的學習順序。可能會有很多種正確的順序, 只要返回其中一種就行。若不可能完成所有課程, 則返回空 list。
Solution 1：
想法：利用 Topological Sort + BFS, 同 207. Course Schedule
class Solution {public: vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { ...
684. Redundant Connection
題目網址：https://leetcode.cn/problems/redundant-connection/
題意：給一 n 個 node 的 tree（編號從 1 到 n）, 並在其中添加一條邊。添加的邊其兩個頂點包含在 1 到 n 中間, 且這條邊不屬於 tree 中已存在的邊。edges[i] = [a, b] 表示圖中 a 和 b 之間存在一條邊。
找出一條可以刪去的邊, 刪除後可使得剩餘部分為 tree。如果有多個答案, 則返回這些答案在 edges 中順序最後的那條邊。
Solution 1：
想法：同 261. Graph Valid Tree, 利用 DFS, 每次加入一條 edge e, 就檢查是否有 cycle, 一旦發現了 cycle, 就返回 e（最後加入形成 cycle 的 edge）
令 e 的兩端點分別為 u、v, 檢查是否已經有 path 能連接 u、v。若有, 則代表加入 e 後會形成 cycle
由於為無向圖, 所以遞迴遍歷時需要用 visited 紀錄哪些 node 已經拜訪過, 一旦拜訪過就不再遞迴遍歷。假設 edge e = [u, ...
323. Number of Connected Components in an Undirected Graph
題目網址：https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/
題意：有一含 n 個 node 的 graph, 給你一整數 n 和 edges, 其中 edges[i] = [a, b] 代表 graph 中 a 和 b 之間有一邊, 返回 connected component 個數。
Solution 1：
想法：利用 DFS, 依序對所有 node 做 dfs, 每次判斷該 node 是否被拜訪過, 若還沒代表有新的 component
e.g. n = 5, edges = [[0, 1], [1, 2], [3, 4]]
先對 0 做 dfs 得到第一個 component(0,1,2), 同時 visited[0,1,2] 都被設為 true
因為 visited[3] = false, 所以對 3 做 dfs 得到第二個 component(3,4)
class Solution {public: int countCo ...