# Graphs (13)
> 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主
>
> 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)
<!-- 常用色碼紀錄
Easy: <font color="#00ad5f">**Easy**</font>
Medium: <font color="#ffbb00">**Medium**</font>
Hard: <font color="#ee2f56">**Hard**</font>
-->
## Introduction
### 1. Breath-First-Search (BFS)
以 doubly queue 實作，當 doubly queue $q$不為空時
* 取出一個頂點 $v$ 拜訪
* 對頂點 $v$ 的未拜訪鄰居
* 將未拜訪的鄰居頂點加到 $q$ 中
* 標記為已拜訪
重複上述步驟直到 $q$ 為空
### 2. Depth-First-Search(DFS)
以 stack 實作，類似樹的 preorder traversal，當 stack $S$ 不為空時
* 取出一個頂點 $v$ 拜訪
* 對頂點 $v$ 的未拜訪鄰居
* 將未拜訪的鄰居頂點加到 $S$ 中
* 標記為已拜訪
重複上述步驟直到 $S$ 為空
## 1. Number of Islands
<font color="#ffbb00">**Medium**</font>
> Given a 2D grid `grid` where `'1'` represents land and `'0'` represents > water, count and return the number of islands.
>
> An **island** is formed by connecting adjacent lands horizontally or > vertically and is surrounded by water. You may assume water is > surrounding the grid (i.e., all the edges are water).
### Example 1:
```java
Input: grid = [
["0","1","1","1","0"],
["0","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
```
### Example 2:
```java
Input: grid = [
["1","1","0","0","1"],
["1","1","0","0","1"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 4
```
### Constraints
* `1 <= grid.length, grid[i].length <= 100`
* `grid[i][j]` is `'0'` or `'1'`.
### Recommended complexity
* Time complexity: $O(m \cdot n)$
* m is the number of rows
* n is the number of columns
* Space complexity: $O(m \cdot n)$
### Solution
走訪整個地圖，當遇到 `'1'` 時就從該點開始使用 DFS 或 BFS 搜索並走訪至其他相鄰的 `'1'`，直到把該 group/island 歷遍。走訪完該 island 後再將 island 的數量 +1。
為避免走訪至相同的位置，使用一個 hash set 來紀錄走過的位置(`(row, col)`)
#### 1. DFS with recursion ver.
```python=
# DFS(recursion ver.)
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
rows, cols = len(grid), len(grid[0])
visited = set() # (row, col)
islands = 0
def dfs(r, c):
visited.add((r, c))
directions = [(0, 1), (0, -1), (-1, 0), (1, 0)] # up, down, left, right
for dr, dc in directions:
newR, newC = r + dr, c + dc
if (newR in range(rows) and
newC in range(cols) and
(newR, newC) not in visited and
grid[newR][newC] == "1"):
dfs(newR, newC)
# traversal entire graph
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r, c) not in visited:
dfs(r, c)
islands += 1
return islands
```
#### 2. DFS with stack ver.
```python=
# DFS(stack ver.)
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
rows, cols = len(grid), len(grid[0])
visited = set() # (row, col)
islands = 0
def dfs(r, c):
stack = []
stack.append((r, c))
visited.add((r, c))
while stack:
row, col = stack.pop()
directions = [(0, 1), (0, -1), (-1, 0), (1, 0)] # up, down, left, right
for dr, dc in directions:
newR, newC = row + dr, col + dc
if (newR in range(rows) and
newC in range(cols) and
(newR, newC) not in visited and
grid[newR][newC] == "1"):
stack.append((newR, newC))
visited.add((newR, newC))
# traversal entire graph
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r, c) not in visited:
dfs(r, c)
islands += 1
return islands
```
#### 3. BFS with queue ver.
```python=
# BFS
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
rows, cols = len(grid), len(grid[0])
visited = set() # (row, col)
islands = 0
def bfs(r, c):
q = collections.deque()
q.append((r, c))
visited.add((r, c))
while q:
row, col = q.popleft()
directions = [(0, 1), (0, -1), (-1, 0), (1, 0)] # up, down, left, right
for dr, dc in directions:
newR, newC = row + dr, col + dc
if (newR in range(rows) and # not exceed row
newC in range(cols) and # not exceed col
(newR, newC) not in visited and
grid[newR][newC] == "1"):
q.append((newR, newC))
visited.add((newR, newC))
# traversal entire graph
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r, c) not in visited:
bfs(r, c)
# visited.add((r, c))
islands += 1
return islands
```
## 2. Max Area of Islands
<font color="#ffbb00">**Medium**</font>
> You are given a matrix `grid` where `grid[i]` is either a `0` (representing water) or `1` (representing land).
>
> An island is defined as a group of `1`'s connected horizontally or vertically. You may assume all four edges of the grid are surrounded by water.
>
> The **area** of an island is defined as the number of cells within the island.
>
> Return the maximum area of an island in `grid`. If no island exists, return `0`.
### Example 1:
```java
Input: grid = [
[0,1,1,0,1],
[1,0,1,0,1],
[0,1,1,0,1],
[0,1,0,0,1]
]
Output: 6
```
Explanation: `1`'s cannot be connected diagonally, so the maximum area of the island is `6`.
### Constraints
* `1 <= grid.length, grid[i].length <= 50`
### Recommended complexity
* Time complexity: $O(m \cdot n)$
* m is the number of rows
* n is the number of columns
* Space complexity: $O(m \cdot n)$
### Solution
基本與前一題的方法相同，但因為要計算面積，所以在拜訪時如果該位置是 land 則面積 + 1。面積的計算有 2 種方式可以選擇：
1. 把面積 `area` 作為引數傳入`bfs()`/`dfs()` 中(以下使用這個)
2. 或是在遞迴時回傳面積走訪過的 land 的面積再 +1(當前 land 的面積)
```python=
# dfs(recursion ver.)
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
visited = set() # (row, col)
maxArea = 0
def dfs(r, c, area):
visited.add((r, c))
area += 1
directions = [(1, 0), (-1, 0), (0, -1), (0, 1)] # up, down, left, right
for dr, dc in directions:
newR, newC = r + dr, c + dc
if (newR in range(rows) and
newC in range(cols) and
(newR, newC) not in visited and
grid[newR][newC] == 1):
area = dfs(newR, newC, area)
return area
for r in range(rows):
for c in range(cols):
if ((r, c) not in visited and
grid[r][c] == 1):
currArea = dfs(r, c, 0)
maxArea = max(maxArea, currArea)
return maxArea
```
## 3. Clone Graph
<font color="#ffbb00">**Medium**</font>
> Given a node in a connected undirected graph, return a deep copy of the graph.
>
> Each node in the graph contains an integer value and a list of its neighbors.
```java
class Node {
public int val;
public List<Node> neighbors;
}
```
> The graph is shown in the test cases as an adjacency list. **An adjacency list** is a mapping of nodes to lists, used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
>
> For simplicity, nodes values are numbered from 1 to `n`, where `n` is the total number of nodes in the graph. The index of each node within the adjacency list is the same as the node's value (1-indexed).
>
> The input node will always be the first node in the graph and have `1` as the value.
### Example 1:
<img src="https://hackmd.io/_uploads/S1_Rs6yKyg.png" width=300>
```java
Input: adjList = [[2],[1,3],[2]]
Output: [[2],[1,3],[2]]
```
Explanation: There are 3 nodes in the graph.
Node 1: val = 1 and neighbors = [2].
Node 2: val = 2 and neighbors = [1, 3].
Node 3: val = 3 and neighbors = [2].
### Example 2:
<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/96c7fb34-26e8-42e0-5f5d-61b8b8c96800/public" width=100>
```java
Input: adjList = [[]]
Output: [[]]
```
Explanation: The graph has one node with no neighbors.
### Example 3:
```java
Input: adjList = []
Output: []
```
Explanation: The graph is empty.
### Constraints
* `0 <= The number of nodes in the graph <= 100.`
* `1 <= Node.val <= 100`
* There are no duplicate edges and no self-loops in the graph.
### Recommended complexity
* Time complexity: $O(V+E)$
* V is the number of vertices
* E is the number of edges
* Space complexity: $O(E)$
### Solution
使用 DFS 走訪整個圖，每走訪到一個新(未拜訪)的頂點($u$)就建立/複製一個新節點($u'$)，再走訪到該頂點($u$)的相鄰頂點($v$)。
當走訪到相鄰頂點($v$)且複製新的節點($v'$)後，因為是 undirected graph 所以 $v'$ 需要回頭連接前一個頂點 $u'$。此時可以利用一個 hash map 找到前一個頂點 $u'$，該 hash map 儲存複製前與複製後的頂點對 $(u, u')$。
此外，該 hash map 亦可用來作為 `visited` 使用，因為只有拜訪過的頂點會被複製並儲存到 hash map 中，沒有被複製的頂點就是沒被拜訪過。
```python=
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
oldToNew = {}
def dfs(node):
if node in oldToNew:
return oldToNew[node]
copy = Node(node.val)
oldToNew[node] = copy
for nbr in node.neighbors:
copy.neighbors.append(dfs(nbr))
return copy
return dfs(node) if node else None
```
> [!Note]
> Leetcode/Neetcode 題目本身的測資已經建立好圖的結構，傳入的只是圖的其中一個頂點而非整張圖的 adjList 表示法。
## 4. Walls and Gates
<font color="#ffbb00">**Medium**</font>
> You are given a $m \cdot n$ 2D `grid` initialized with these three possible values:
>
> 1. `-1` - A water cell that can not be traversed.
> 2. `0` - A treasure chest.
> 3. `INF` - A land cell that can be traversed. We use the integer `2^31 - 1 = 2147483647` to represent `INF`.
>
> Fill each land cell with the distance to its nearest treasure chest. If a land cell cannot reach a treasure chest than the value should remain `INF`.
>
> Assume the grid can only be traversed up, down, left, or right.
>
> Modify the `grid` **in-place**.
### Example 1:
```java
Input: [
[2147483647,-1,0,2147483647],
[2147483647,2147483647,2147483647,-1],
[2147483647,-1,2147483647,-1],
[0,-1,2147483647,2147483647]
]
Output: [
[3,-1,0,1],
[2,2,1,-1],
[1,-1,2,-1],
[0,-1,3,4]
]
```
### Example 2:
```java
Input: [
[0,-1],
[2147483647,2147483647]
]
Output: [
[0,-1],
[1,2]
]
```
### Constraints
* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 100`
* `grid[i][j]` is one of `{-1, 0, 2147483647}`
### Recommended complexity
* Time complexity: $O(m \cdot n)$
* m is the number of rows
* n is the number of columns
* Space complexity: $O(m \cdot n)$
### Solution
#### 1. Brute force
迭代整個圖，每當找到一個 land(`INF`) 就走訪所有路徑直到遇到 treasure(`0`) 後紀錄路徑長，迭代完整張圖再比較每個 `INF` 點的路徑長並選擇最小值。
上述方法是 brute force solution，因為迭代整張圖的每個點需要 $O(m \cdot n)$ 的時間，每個點又需要去走訪所有位置計算路徑長，時間也是 $O(m \cdot n)$，
所以時間複雜度為 $O((m \cdot n)^2)$
#### 2. Improvement: multi-source BFS
可以從 `0` 的地方逆向著手，找到 `0` 的位置後從該點往外開始做搜索走訪所有的 `INF` 並逐步紀錄路徑長。
這題實際上是做多起點(multi-source)的 BFS，類似最短路徑問題。而 BFS 的走訪方式本身很適合尋找最短路徑問題。下為解題步驟：
* 迭代整張圖找到所有 `0` 的位置作為搜索的起點
* 從所有 `0` 的位置**同時**出發並往相鄰的頂點做 BFS 的逐層搜索(level search)
* 為了模擬每個位置的**同時**搜索，相同階層的位置需使用一個 `for` 迴圈從 queue 中依次取出拜訪
* 拜訪時更新每個點與 `0` 的距離
* 並添加下一階層(相鄰)頂點的位置到 queue 中
```python=
class Solution:
def islandsAndTreasure(self, grid: List[List[int]]) -> None:
rows, cols = len(grid), len(grid[0])
INF = 2147483647
visited = set() # (r, c)
q = collections.deque() # (r, c)
def bfs(r, c):
if (0 <= r < rows and
0 <= c < cols and
(r, c) not in visited and
grid[r][c] == INF):
q.append((r, c))
visited.add((r, c))
# iterate whole graph and find all treasures
for r in range(rows):
for c in range(cols):
if grid[r][c] == 0:
q.append((r, c))
visited.add((r, c))
dist = 0
while q:
# search from each land at same time
for _ in range(len(q)):
r, c = q.popleft()
# add next level node
bfs(r + 1, c) # up
bfs(r - 1, c) # down
bfs(r, c - 1) # left
bfs(r, c + 1) # right
# update distance between treasure and each land
grid[r][c] = dist
dist += 1
```
## 5. Rotting Oranges
<font color="#ffbb00">**Medium**</font>
> You are given a 2-D matrix `grid`. Each cell can have one of three possible values:
>
> * `0` representing an empty cell
> * `1` representing a fresh fruit
> * `2` representing a rotten fruit
>
> Every minute, if a fresh fruit is horizontally or vertically adjacent to a rotten fruit, then the fresh fruit also becomes rotten.
>
> Return the minimum number of minutes that must elapse until there are zero fresh fruits remaining. If this state is impossible within the grid, return `-1`.
### Example 1:
```java
Input: grid = [[1,1,0],[0,1,1],[0,1,2]]
Output: 4
```
### Example 2:
```java
Input: grid = [[1,0,1],[0,2,0],[1,0,1]]
Output: -1
```
### Constraints
* `1 <= grid.length, grid[i].length <= 10`
### Recommended complexity
* Time complexity: $O(m \cdot n)$
* m is the number of rows
* n is the number of columns
* Space complexity: $O(m \cdot n)$
### Solution
類似前一題的 multi-source BFS，但從 rotten(`2`)出發後可能有某些點無法走訪(即題目所說的 impossible state)，所以需要一個變數 `fresh` 追蹤目前還有多少個 fresh fruit 應該走訪但還沒碰到。又因為 `fresh` 是區域變數，在函式內的修改無法傳遞出去(除非作為引數一同傳入函式中)，所以使用 `for` 迴圈模擬前一題的 `bfs()` 函式。
每當位置加到佇列 `q` 中，就表示該位置的水果已被感染(rotten)，`fresh -= 1`。`while` 迴圈繼續執行的條件除了佇列 `q` 非空之外，還需要加上 `fresh > 0`，否則在最後會多算一次的時間。
```python=
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
visited = set()
q = collections.deque()
fresh = 0
# find rotten and count fresh fruit
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
q.append((r, c))
visited.add((r, c))
if grid[r][c] == 1:
fresh += 1
time = 0
while q and fresh > 0:
for _ in range(len(q)):
r, c = q.popleft()
# grid[r][c] = 2
# bfs
directions = [(1, 0), (-1, 0), (0, -1), (0, 1)] # up, down, left, right
for dr, dc in directions:
newR, newC = r + dr, c + dc
if (newR < 0 or newR >= rows or
newC < 0 or newC >= cols or
(newR, newC) in visited or
grid[newR][newC] != 1):
continue
q.append((newR, newC))
visited.add((newR, newC))
fresh -= 1
time += 1
if fresh > 0:
return -1
else:
return time
```
## 6. Pacific Atlantic Water Flow
<font color="#ffbb00">**Medium**</font>
> You are given a rectangular island `heights` where `heights[r][c]` represents the height above sea level of the cell at coordinate `(r, c)`.
>
> The islands borders the **Pacific Ocean** from the top and left sides, and borders the **Atlantic Ocean** from the bottom and right sides.
>
> Water can flow in four directions (up, down, left, or right) from a cell to a neighboring cell with **height equal or lower**. Water can also flow into the ocean from cells adjacent to the ocean.
>
> Find all cells where water can flow from that cell to both the Pacific and Atlantic oceans. Return it as a **2D list** where each element is a list *[r, c]* representing the row and column of the cell. You may return the answer in **any order**.
### Example 1:
```java
Input: heights = [
[4,2,7,3,4],
[7,4,6,4,7],
[6,3,5,3,6]
]
Output: [[0,2],[0,4],[1,0],[1,1],[1,2],[1,3],[1,4],[2,0]]
```
### Example 2:
```java
Input: heights = [[1],[1]]
Output: [[0,0],[0,1]]
```
### Constraints
* `1 <= heights.length, heights[r].length <= 100`
* `0 <= heights[r][c] <= 1000`
### Recommended complexity
* Time complexity: $O(m \cdot n)$
* m is the number of rows
* n is the number of columns
* Space complexity: $O(m \cdot n)$
### Solution
#### 1. Brute force
迭代整張圖的每個點，並從每個點出發去尋找能同時到達 Pacific 與 Atlantic 的路徑。但時間複雜度為 $O((m \cdot n))^2$
#### 2. Improvement
參考 multi-source 的做法從反向著手。從其中一個海洋(左上/右下)出發，如果可以抵達另一個海洋(右下/左上)則該路徑上的點即為所求。使用兩個 hash set 分別儲存從 Pacific 和 Atlantic 出發的路徑並使用 DFS 搜索與 Pacific/Atlantic 相鄰的邊(左上/右下)的所有位置。
因為是從反向思考著手，所以下一個位置的高度**大於等於**當前位置才會繼續遞迴，反之則往其他位置搜索。最後將兩個 hash set 取交集即為所求。
```python=
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
rows, cols = len(heights), len(heights[0])
pacific = set()
atlantic = set()
leftTop = []
for r in range(rows):
if r == 0:
for c in range(cols):
leftTop.append((r, c))
else:
leftTop.append((r, 0))
rightBottom = []
for r in range(rows):
if r == (rows - 1):
for c in range(cols):
rightBottom.append((r, c))
else:
rightBottom.append((r, cols-1))
def dfs(r, c, visited):
if (r, c) in visited:
return
visited.add((r, c))
directions = [(1, 0), (-1, 0), (0, -1), (0, 1)]
for dr, dc in directions:
newR, newC = r + dr, c + dc
if (newR < 0 or newR >= rows or
newC < 0 or newC >= cols or
heights[newR][newC] < heights[r][c]):
continue
dfs(newR, newC, visited)
for pr, pc in leftTop:
dfs(pr, pc, pacific)
for ar, ac in rightBottom:
dfs(ar, ac, atlantic)
return list(pacific & atlantic)
```
> [!Warning]
> 在 Python 中，元組(tuple)、串列(list)、集合(set)等物件在函式中是以 passby reference 的方式傳遞，所以函式內部修改 `visited` 的動作會直接反應到傳入的引數(`pacific` 與 `atlantic`)，因此遞迴的過程不用回傳值。
>
> 但若是要模擬 passby value 的方式傳遞 `visited`，則需要在呼叫 `bfs()` 後回傳一個集合(set)，但集合之間不能用 `add()` 方法添加，應該使用 `union()` 方法合併遞迴結果。
## 7. Surrounding Regions
<font color="#ffbb00">**Medium**</font>
> You are given a 2-D matrix `board` containing `'X'` and `'O'` characters.
>
> If a continous, four-directionally connected group of `'O'`s is surrounded by `'X'`s, it is considered to be **surrounded**.
>
> Change all **surrounded** regions of `'O'`s to `'X'`s and do so in-place by modifying the input board.
### Example 1:
```java
Input: board = [
["X","X","X","X"],
["X","O","O","X"],
["X","O","O","X"],
["X","X","X","O"]
]
Output: [
["X","X","X","X"],
["X","X","X","X"],
["X","X","X","X"],
["X","X","X","O"]
]
```
Explanation: Note that regions that are on the border are not considered surrounded regions.
### Constraints
* `1 <= board.length, board[i].length <= 200`
* `board[i][j]` is `'X'` or `'O'`.
### Recommended complexity
* Time complexity: $O(m \cdot n)$
* Space complexity: $O(m \cdot n)$
* m is the number of rows
* n is the number of columns
### Solution
如果一個 O 能夠透過上下左右到達邊界，則該區域就不算是 surrounded。，因此需要找到不會透過四個方向(上下左右)連接到矩陣邊界上的 O 的區域，才算是被 surrounded。
參考前一題的方式，從邊界開始出發，如果邊界上的 O 能夠回推並連接到某個區域的 O，則該區域沒有被包圍。
#### Ver. 1 - need additional memory
第一種方式與前一題類似，使用 hash set(`visited`) 紀錄走過且沒有被包圍的位置，但需要耗費額外的記憶體空間儲存 hash set。
```python=
class Solution:
def solve(self, board: List[List[str]]) -> None:
rows, cols = len(board), len(board[0])
visited = set()
def dfs(r, c):
if (r < 0 or r >= rows or
c < 0 or c >= cols or
(r, c) in visited or
board[r][c] != 'O'):
return
visited.add((r, c)) # add to viisted if board[r][c] is 'O'
dfs(r + 1, c) # up
dfs(r - 1, c) # down
dfs(r, c - 1) # left
dfs(r, c + 1) # right
# iterate the border row by row
for r in range(rows):
if (r == 0) or (r == rows - 1): # if first or last row
for c in range(cols): # iterate all column
if board[r][c] == 'O':
dfs(r, c)
else: # if NOT first or last row
if board[r][0] == 'O': # find first and last column
dfs(r, 0)
if board[r][cols-1] == 'O':
dfs(r, cols-1)
# convert 'O' located on (r, c) into 'X' if (r, c) not in visited
for r in range(rows):
for c in range(cols):
if (r, c) in visited:
continue
board[r][c] = 'X'
```
#### Ver. 2 - in place
第二種方式將走過且沒有被 surrounded 的位置標記為 `'E'`，以此取代 hash set `visited`，但最後要記得將 `'E` 轉回 `'O'`。
```python=
class Solution:
def solve(self, board: List[List[str]]) -> None:
rows, cols = len(board), len(board[0])
# visited = set()
def dfs(r, c):
if (r < 0 or r >= rows or
c < 0 or c >= cols or
board[r][c] != 'O'):
return
board[r][c] = 'E' # unsurrounded cell
dfs(r + 1, c) # up
dfs(r - 1, c) # down
dfs(r, c - 1) # left
dfs(r, c + 1) # right
# iterate the border row by row
for r in range(rows):
if (r == 0) or (r == rows - 1): # if first or last row
for c in range(cols): # iterate all column
if board[r][c] == 'O':
dfs(r, c)
else: # if NOT first or last row
if board[r][0] == 'O': # find first and last column
dfs(r, 0)
if board[r][cols-1] == 'O':
dfs(r, cols-1)
# convert 'O' located on (r, c) into 'X'
for r in range(rows):
for c in range(cols):
if board[r][c] == 'O':
board[r][c] = 'X'
elif board[r][c] == 'E':
board[r][c] = 'O'
```
## 8. Course Schedule
<font color="#ffbb00">**Medium**</font>
> You are given an array `prerequisites` where `prerequisites[i] = [a, b]` indicates that you **must** take course `b` first if you want to take course `a`.
>
> The pair `[0, 1]`, indicates that must take course `1` before taking course `0`.
>
> There are a total of `numCourses` courses you are required to take, labeled from `0` to `numCourses - 1`.
>
> Return `true` if it is possible to finish all courses, otherwise return `false`.
### Example 1:
```java
Input: numCourses = 2, prerequisites = [[0,1]]
Output: true
```
Explanation: First take course 1 (no prerequisites) and then take course 0.
### Example 2:
```java
Input: numCourses = 2, prerequisites = [[0,1],[1,0]]
Output: false
```
Explanation: In order to take course 1 you must take course 0, and to take course 0 you must take course 1. So it is impossible.
### Constraints
* `1 <= numCourses <= 1000`
* `0 <= prerequisites.length <= 1000`
* All `prerequisite` pairs are **unique**.
### Recommended complexity
* Time complexity: $O(V + E)$
* Space complexity: $O(V + E)$
* V is the number of courses(nodes)
* E is the number of prerequisites(edges)
### Solution
討論課程間的先後順序關係可用圖(graph)，且又因為兩門課程有先後順序的關係，所以是一個方向圖(directed graph)。考慮到所有課程都需要完成，所以如果此圖具有 cycle 的結構則課程就無法完成。
可以使用 DFS 走訪整個圖來判斷有無 cycle 結構。從某一門課開始，完成其先修課程並不斷往前遞迴。使用一個 hash set 紀錄有沒有走過某個節點，如果走訪過程中走到一個重複的節點，則表示此圖有 cycle 結構。
不論使用 DFS 或 BFS 走訪，都需要先建立此圖的 adjacent list 表示法才能夠進行走訪。根據 adjacent list 的結構，可以使用一個 hash map 來表示。以下面的 adjList 為例：
```
# Graph
0 ---> 1 ---> 3 ---> 4
| | ^
| |-------------|
|
|--->2
# adjList
0 --> [1, 2]
1 --> [3, 4]
2 --> []
3 --> [4]
4 --> []
```
DFS 走訪的過程其實就是一個修課地圖的路徑：
* 對於每個節點，利用迭代去歷遍所有它的所有相鄰點(先修課程)
* 使用一個 hash set 紀錄目前正在走的路徑中有沒有重複的點
* 當所有先修課程(相鄰點)都走完，則從 hash set 中移除該點(因為不會再走這條路線了)
* 當某節點的所有先修課程(相鄰點)都走完，則將相鄰點設為空的串列 `[]`
因為修課路徑可能是一個 disconnected graph，有些課程可能是獨立的沒有先後順序，所以最後要迭代所有的頂點才能歷遍整個圖。
```python=
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# build adjList by hash map
courseMap = {i:[] for i in range(numCourses)}
for course, prev in prerequisites:
courseMap[course].append(prev)
path = set()
def dfs(course):
if course in path: # detect cycle
return False
if courseMap[course] == []: # this course can finish
return True
path.add(course)
for pre in courseMap[course]:
if not dfs(pre): # detest cycle
return False
path.remove(course) # all neighbor visited, then remove this course from path
courseMap[course] = [] # finish this course
return True
for course in range(numCourses):
if not dfs(course):
return False
return True
```
## 9. Course Schedule II
<font color="#ffbb00">**Medium**</font>
> You are given an array `prerequisites` where `prerequisites[i] = [a, b]` indicates that you **must** take course `b` first if you want to take course `a`.
>
> * For example, the pair `[0, 1]`, indicates that to take course `0` you have to first take course `1`.
>
> There are a total of `numCourses` courses you are required to take, labeled from `0` to `numCourses - 1`.
>
> Return a valid ordering of courses you can take to finish all courses. If there are many valid answers, return any of them. If it's not possible to finish all courses, return an **empty array**.
### Example 1:
```java
Input: numCourses = 3, prerequisites = [[1,0]]
Output: [0,1,2]
```
Explanation: We must ensure that course 0 is taken before course 1.
### Example 2:
```java
Input: numCourses = 3, prerequisites = [[0,1],[1,2],[2,0]]
Output: []
```
Explanation: It's impossible to finish all courses.
### Constraints
* `1 <= numCourses <= 1000`
* `0 <= prerequisites.length <= 1000`
* All `prerequisite` pairs are **unique**.
### Recommended complexity
* Time complexity: $O(V + E)$
* Space complexity: $O(V + E)$
* V is the number of courses(nodes)
* E is the number of prerequisites(edges)
### Solution
與前一題做法類似，使用 DFS 走訪所有的頂點，且對走訪過的點使用 topological sort 排序，並在這過程中檢查有沒有 cycle。
針對每個節點的走訪都會有以下狀況：
* 在 cycle 結構的檢查中有沒有被拜訪過(`cycle`)
* 在整個 graph 的走訪中有沒有被拜訪過(`visited`)
使用兩個 hash set() 來紀錄上述的走訪過程(`cycle` 相當於前一題的 `visited`)
```python=
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# build adjList by hash map
courseMap = {i:[] for i in range(numCourses)}
for course, prev in prerequisites:
courseMap[course].append(prev)
visited = set()
cycle = set()
output = []
def dfs(course):
# check cycle
if course in cycle:
return False
# check repeat
if course in visited:
return True
# go through all neighbors
cycle.add(course)
visited.add(course)
for prev in courseMap[course]:
if dfs(prev) == False: # have cycle
return False
# have no cycle
cycle.remove(course)
output.append(course)
return True
for course in range(numCourses):
if not dfs(course):
return []
return output
```
> [!Note] **Topological Sort (拓樸排序)**
> 某些具有先後關係的事項能夠用 directed graph 表示並用 topological sort 將先後順序列出。且因為節點之間具有絕對的優先順序，所以只有不含 cycle 的有向圖(directed acyclic graph, DAG)才能夠使用。
> Topoligical sort 是根據先後順序排列，但有時並不是所有點都具有先後順序關係(可能是獨立的)，所以 topological sort 的結果不是唯一。
>
> 能夠使用 DFS 來模擬 topological sort：
> * 從某個節點開始做 DFS
> * 如果該節點已經被拜訪，則拜訪它的相鄰點(neighbor)
> * 如果該點的所有相鄰點都已經被拜訪過，則將該點 push 到一個 stack 之中
> * 當所有節點都走過，則從 top 端開始將 stack 中的節點依序 pop 出來，pop 的順序即為 topological sort 的結果
>
> 
> (圖片來源: [GeeksForGeeks](https://www.geeksforgeeks.org/topological-sorting/?ref=gcse_outind))
## 10. Graph Valid Tree
<font color="#ffbb00">**Medium**</font>
> Given `n` nodes labeled from `0` to `n - 1` and a list of **undirected** edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
### Example 1:
```java
Input:
n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output:
true
```
### Example 2:
```java
Input:
n = 5
edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output:
false
```
### Constraints
* `1 <= n <= 100`
* `0 <= edges.length <= n * (n - 1) / 2`
### Recommended complexity
* Time complexity: $O(V + E)$
* Space complexity: $O(V + E)$
* V is the number of courses(nodes)
* E is the number of prerequisites(edges)
### Solution
> [!Note] **Thm**
> * An undirected graph is a tree if it is connected and does not contain cycle
> * Let G be an undirected graph on n nodes. Any two of the following statements imply the third.
> 1. G is connected.
> 2. G does not contain a cycle.
> 3. G has n - 1 edges.
根據上述定理，只要一個 undirected graph 滿足上述條件中的其中兩個，就可稱為是一個 tree。
#### Ver. 1
第一種版本使用 1. 與 3. 兩條件。Connected 的檢驗只要使用 DFS 走完整張圖，如果走過的節點數 = 圖的節點數就表示是 connected graph。建立 adjacent list 時因為是 undirected，所以每條邊都要雙向都要各建立一次。
```python=
# ver. 1
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
adjList = {i:[] for i in range(n)}
for node1, node2 in edges:
adjList[node1].append(node2)
adjList[node2].append(node1)
visited = set()
def dfs(node):
if node in visited:
return
visited.add(node)
for nbr in adjList[node]:
dfs(nbr)
dfs(0)
if (len(edges) == n - 1) and (len(visited) == n):
return True
else:
return False
```
#### Ver. 2
第二種版本使用 1. 與 2. 兩條件。檢測undirected graph 有無 cycle 的方式與 directed graph 類似，但在找相鄰點時可能會找到它的前一個導致判斷錯誤，以下面的圖為例
```
1 - 0 - 4
|
2 - 3
```
從 `dfs(0)` 開始，第一個相鄰點是 `1`，往下開始遞迴 `dfs(1)`。接下來 `dfs(1)` 的第一個相鄰點是 `0`，但 `0` 已經被走過，此時會就可能會被誤判為 cycle。此問題可以透過在 `dfs()` 中多傳遞一個參數表示前一個節點(parent)，在找相鄰點時，如果遇到前一個 parent 節點就跳過。起始點因為沒有 parent 節點，所以用 `-1` 表示。
```python=
# ver. 2
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
adjList = {i:[] for i in range(n)}
for node1, node2 in edges:
adjList[node1].append(node2)
adjList[node2].append(node1)
visited = set()
def dfs(node, prev):
if node in visited:
return False
visited.add(node)
for nbr in adjList[node]:
if nbr == prev:
continue
if not dfs(nbr, node):
return False
return True
if (dfs(0, -1)) and (len(visited) == n):
return True
else:
return False
```
## 11. Number of Connected Components In An Undirected Graph
<font color="#ffbb00">**Medium**</font>
> There is an undirected graph with `n` nodes. There is also an `edges` array, where `edges[i] = [a, b]` means that there is an edge between node `a` and node `b` in the graph.
>
> The nodes are numbered from `0` to `n - 1`.
>
> Return the total number of connected components in that graph.
### Example 1:
```java
Input:
n=3
edges=[[0,1], [0,2]]
Output:
1
```
### Example 2:
```java
Input:
n=6
edges=[[0,1], [1,2], [2,3], [4,5]]
Output:
2
```
### Constraints
* `1 <= n <= 100`
* `0 <= edges.length <= n * (n - 1) / 2`
### Recommended complexity
* Time complexity: $O(V + E)$
* Space complexity: $O(V + E)$
* V is the number of courses(nodes)
* E is the number of prerequisites(edges)
### Solution
迭代所有節點，如果某節點沒有走訪過，就使用 DFS 以該點為起點遞迴且計數器(`count`) + 1。如果該節點走過則跳往下一個繼續迭代。最後根據拜訪過的節點(`visited`)的長度決定是否已將整張圖走過。當整張圖走完 `count` 即為所求。
```python=
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
adjList = {i:[] for i in range(n)}
for node1, node2 in edges:
adjList[node1].append(node2)
adjList[node2].append(node1)
visited = [False] * n
def dfs(node):
for nbr in adjList[node]:
if not visited[nbr]:
visited[nbr] = True
dfs(nbr)
count = 0
for node in range(n):
if not visited[node]:
dfs(node)
count += 1
return count
```
如果要繼續針對程式碼優化，可以將 hash set 改為 array，降低查找的時間($O(V)$ 變為 $O(1)$)。
```python=
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
adjList = {i:[] for i in range(n)}
for node1, node2 in edges:
adjList[node1].append(node2)
adjList[node2].append(node1)
visited = [False] * n
def dfs(node):
for nbr in adjList[node]:
if not visited[nbr]:
visited[nbr] = True
dfs(nbr)
count = 0
for node in range(n):
if not visited[node]:
visited[node] = True
dfs(node)
count += 1
return count
```
## 12. Redundant Connection
<font color="#ffbb00">**Medium**</font>
> You are given a connected **undirected graph** with `n` nodes labeled from `1` to `n`. Initially, it contained no cycles and consisted of `n-1` edges.
>
> We have now added one additional edge to the graph. The edge has two `different` vertices chosen from `1` to `n`, and was not an edge that previously existed in the graph.
>
> The graph is represented as an array `edges` of length `n` where `edges[i] = [ai, bi]` represents an edge between nodes `ai` and `bi` in the graph.
>
> Return an edge that can be removed so that the graph is still a connected non-cyclical graph. If there are multiple answers, return the edge that appears last in the input `edges`.
### Example 1:
```java
Input: edges = [[1,2],[1,3],[3,4],[2,4]]
Output: [2,4]
```
### Example 2:
```java
Input: edges = [[1,2],[1,3],[1,4],[3,4],[4,5]]
Output: [3,4]
```
### Constraints
* `n == edges.length`
* `3 <= n <= 100`
* `1 <= edges[i][0] < edges[i][1] <= edges.length`
* There are no repeated edges and no self-loops in the input.
### Recommended complexity
* Time complexity: $O(V + E)$
* Space complexity: $O(V + E)$
* V is the number of courses(nodes)
* E is the number of prerequisites(edges)
### Solution
> [!Note] **Disjoint set**
> Disjoint set 又稱為 Union-Find algorithm，用來尋找兩個互斥的集合，支援以下 2 個運算：
>
> * 透過 `union(n1, n2)` 將分屬兩個集合的元素合併為單一集合
> * 透過 `find()` 尋找某個節點所在集合的代表元素
> * `find()` 運算也可用來判斷兩個集合是否互斥，若兩個點所在的集合的代表元素相同，表示此兩點是同一個集合
>
> 上述兩種運算需依靠兩個 array 實現
>
> * `parent[]`: 用來紀錄每個集合的代表元素，因為每個 disjoint set 都可視為一個 tree，所以代表元素即為根節點(root)
> * `rank[]`: 紀錄每個集合的大小，當兩個集合合併時，需要將集合大小疊加上去
>
> 以下圖為例，一開始有三個互斥的集合 `[1, 2, 3]`，每個集合大小都是 1，所以 `parent[3] = [1, 2, 3]` 且 `rank[3] = [1, 1, 1]`。
> * 當合併頂點 1 與頂點 2 後，新的集合以 `1` 為根節點形成 `[1, 2]`
> * `parent[3] = [1, 1, 3]`
> * `rank[3] = [2, 1, 1]`
> * 當合併頂點 2 與頂點 3 時
> * 因為兩個分屬不同集合(根節點不同)，所以由小的合併至大的中
> * `parent[3] = [1, 1, 1]`
> * `rank[3] = [3, 1, 1]`
> 
一開始所有的點都是互斥集合，使用 union-find algorithm 從頭開始依據題目給定的邊建立圖。理論上每個邊的兩個頂點在合併前應該分屬不同集合，當出現某個邊的兩個頂點分屬同個集合時，表示這條邊是多餘的，因為此兩點已經 connected。
(1) `find(n)` 用來找節點 n 的根節點
透過不斷迭代往節點 n 的 parent 尋找，當找到某節點是自己的 parent 時，表示此點是這個集合的根節點。
(2) `union(n1, n2)` 用來合併節點 `n1` 與 `n2` 所在的集合
如果兩個節點的根節點相同，表示已經是同一個集合，不用合併。如果 `n1` 所在的集合較大(`rank[p1] > rank[p2]`)，則把 `n2` 所屬集合加入到 `n1` 中，並更新 `n2` 的根節點與 `n1` 所屬集合的 rank。反之亦然。
最後迭代所有邊長建立 undirected graph，如果某個某個邊重複建立，則表示此邊是多餘的。
```python=
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
par = [i for i in range(len(edges) + 1)]
rank = [1] * (len(edges) + 1)
# find root of n an setup it
def find(n):
p = par[n] # parent of n
# if p is parent of itself, return it
while p != par[p]:
par[p] = par[par[p]]
p = par[p]
return p
# merge
def union(n1, n2):
p1, p2 = find(n1), find(n2)
# have same root, so edge (n1, n2) is redundant
if p1 == p2:
return False
if rank[p1] > rank[p2]: # add p2 to p1
par[p2] = p1
rank[p1] += rank[p2]
else: # add p1 to p2
par[p1] = p2
rank[p2] += rank[p1]
return True # merge completed
for n1, n2 in edges:
if not union(n1, n2):
return [n1, n2]
```
## 13. Word Ladder
<font color="#ee2f56">**Hard**</font>
> You are given two words, `beginWord` and `endWord`, and also a list of words `wordList`. All of the given words are of the same length, consisting of lowercase English letters, and are all distinct.
>
> Your goal is to transform `beginWord` into `endWord` by following the rules:
>
> * You may transform `beginWord` to any word within `wordList`, provided that at exactly one position the words have a different character, and the rest of the positions have the same characters.
> * You may repeat the previous step with the new word that you obtain, and you may do this as many times as needed.
>
> Return the **minimum number of words within the transformation sequence** needed to obtain the `endWord`, or `0` if no such sequence exists.
### Example 1:
```java
Input: beginWord = "cat", endWord = "sag", wordList = ["bat","bag","sag","dag","dot"]
Output: 4
```
Explanation: The transformation sequence is `"cat" -> "bat" -> "bag" -> "sag"`
### Example 2:
```java
Input: beginWord = "cat", endWord = "sag", wordList = ["bat","bag","sat","dag","dot"]
Output: 0
```
Explanation: There is no possible transformation sequence from `"cat"` to `"sag"` since the word `"sag"` is not in the wordList.
### Constraints
* `1 <= beginWord.length <= 10`
* `1 <= wordList.length <= 100`
### Recommended complexity
* Time complexity: $O(m^2 \cdot n)$
* Space complexity: $O(m^2 \cdot n)$
### Solution
#### Ver. 1 - DFS
使用 DFS 尋找所有可能的路徑，方法類似尋找 cycle 結構(backtracking)，當找到某條路徑可以抵達 endWord 後計算這條路徑的長度儲存在 `res` 中，回到前一步繼續找其他可能的路徑。最後回傳最小的路徑長。
```python=
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
visited = set()
res = []
def search(ch):
if ch == endWord:
res.append(len(visited) + 1)
return
for i in range(len(wordList)):
if wordList[i] in visited:
continue
if self.checkLen(ch, wordList[i]):
visited.add(wordList[i])
search(wordList[i])
visited.remove(wordList[i])
return
search(beginWord)
if not res:
return 0
else:
return min(res)
def checkLen(self, ch1, ch2):
n = len(ch1)
correct = 0
for i in range(n):
if ch1[i] == ch2[i]:
correct += 1
if correct == n - 1:
return True
else:
return False
```
#### Ver. 2 BFS
這題本質上是在最小路徑問題，而最小路徑問題適合使用 BFS 的方式解決，但必須先建立圖的 adjacent list。
(1) 建立 adjacent list
任兩個字串如果要相鄰，表示只能有一個位置的字元不同，除了依序比較字串的所有字元外也可以使用模式匹配(pattern matching)的方式。以字串 `hit` 為例，能夠與 `hit` 相鄰的字串只有 3 種可能模式
* `* i t`
* `h * t`
* `h i *`
剩下的其他字串可以根據各自的組成對應到不同的匹配模式，並以此建立完整的 adjacent list。以下面為例列出部份的 adjList 與其對應的完整圖形，每對相鄰節點都至少有一組的模式相同。
```
beginWord = "hit"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
adjList:
"* i t" --> []
"h * t" --> ["hit", "hot"]
"h i *" --> []
"* o t" --> ["dot", "lot"]
"h o *" --> []
.
.
.
```
<img src="https://hackmd.io/_uploads/SJ5EvyqKke.jpg" width=500>
(2) BFS
建立好 adjacent list 後就可以對此圖進行 BFS 尋找最短路徑。同樣使用一個 hast set 紀錄走過的位置，且相同層級的相鄰節點必須一次做完才能往下一層級的節點繼續搜索。在尋找相鄰節點時，因為 `adjList` 是用模式匹配的方式建立，所以當前節點的字串也必須先找出它的所有可能的的模式(第 26 行)，再從對應的模式把相鄰節點加入到 queue 中(第 27 行)。
(3) `res` 的處理
相同階層的節點會有相同的距離(相對於起始點)，所以處理完同一層的所有節點前往下一層之前才需要將距離(`res`) + 1，因此 `res` 的處理要放在最外層的迴圈後。
```python=
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
# build adjList
adjList = collections.defaultdict(list)
wordList.append(beginWord)
for word in wordList:
for i in range(len(word)):
pattern = word[:i] + '*' + word[i + 1:] # find pattern
adjList[pattern].append(word)
visited = set()
res = 1
q = collections.deque()
q.append(beginWord)
while q:
for i in range(len(q)):
word = q.popleft()
if word == endWord:
return res
for j in range(len(word)):
pattern = word[:j] + '*' + word[j + 1:]
for nbr in adjList[pattern]:
if nbr in visited:
continue
visited.add(nbr)
q.append(nbr)
res += 1
return 0 # didn't fond
```
Sign in with Wallet
Connect another wallet