# Advanced graphs (6)
> 紀錄 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>
-->
## 1. Network Delay Time
<font color="#ffbb00">**Medium**</font>
> You are given a network of `n` directed nodes, labeled from `1` to `n`. You are also given `times`, a list of directed edges where `times[i] = (ui, vi, ti)`.
>
> * `ui` is the source node (an integer from `1` to `n`)
> * `vi` is the target node (an integer from `1` to `n`)
> * `ti` is the time it takes for a signal to travel from the source to the target node (an integer greater than or equal to `0`).
>
> You are also given an integer `k`, representing the node that we will send a signal from.
>
> Return the **minimum** time it takes for all of the `n` nodes to receive the signal. If it is impossible for all the nodes to receive the signal, return `-1` instead.
### Example 1:
```java
Input: times = [[1,2,1],[2,3,1],[1,4,4],[3,4,1]], n = 4, k = 1
Output: 3
```
### Example 2:
```java
Input: times = [[1,2,1],[2,3,1]], n = 3, k = 2
Output: -1
```
### Constraints
* `1 <= k <= n <= 100`
* `1 <= times.length <= 1000`
### Recomended complexity
* Time complexity: $O(E \cdot \log V)$
* Space complexity: $O(V + E)$
### Solution
本題可用 Dijkstra's algorihm。因為題目只要回傳走完所有節點的最小值即可，所以不用像正規的 Dijkstra's algorihm 一樣設置 array 儲存所有點到 src 的最短距離，只有從頭到尾維護一個 `minDistance` 即可
(1) 根據給定圖的邊長建立 adjList
(2) Dijkstra's algorihm (類似 BFS 但以 priority queue/min heap 實作)
每一次迭代會從 min heap 中取出最小距離(from src)與對應的點(`(d, node)`)，並把所有相鄰點與對應的最小距離 push 到 min heap 中。因為不用紀錄每個點的最小距離，所以不用額外進行比較與更新。
(3) 確定所有節點都走過
若 hash set `visited` 的長度與題目給定的節點數量相同，表示所有節點都走過，若沒有則表示有節點沒有走過，是 disconnected graph。
```python=
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
# build adjList
adjList = collections.defaultdict(list)
for src, dst, wgt in times:
adjList[src].append((dst, wgt))
minHeap = []
visited = set()
minDistance = 0
heapq.heappush(minHeap, (0, k)) # (minDistance, src)
while minHeap:
# we find node with min distance in each iteration
# so we use heap to store node and pop it
d, node = heapq.heappop(minHeap)
if node in visited:
continue
visited.add(node)
minDistance = d
# push all nbr to queue
for nbr, wgt in adjList[node]:
heapq.heappush(minHeap, (minDistance + wgt, nbr))
if len(visited) == n:
return minDistance
else:
return -1
```
> [!Note] **Dijkstra's algorihm**
> * 一種基於 greedy algorithm 的演算法，用來尋找 graph 中任兩點的最短距離問題
> * 每一次的迭代會尋找與當前節點距離最近的節點
> * 找到該節點後再往該節點的方向移動
> * 僅適用在邊長為 non-negative weight 的時候
> * 因為是處理最短路徑(shortest path)問題，所以是以 BFS 的方法做修改
> * 當 weight = 1 時 Dijkstra's algorihm 則退化為傳統最短路徑問題的 BFS
> * Implement
> * Data structure:
> * Adjacent list 用來表示圖的結構
> * Visited hash set 用來紀錄節點有無走訪過
> * Cost array 用來紀錄所有點與起始點(src)間的最短距離
> * Step-by-step
> 1. 將起始點 s 與自己的距離標為 0，其餘點與 s 的距離標為 infinity
> 2. 從 src 開始，尋找整張圖與 src 距離最短的點設為當前節點 u
> * 因為要找整張圖中最小距離的點，所以從 min heap 中取出最小距離(`d`)的點
> 3. 計算/更新 u 的相鄰節點的距離
> * 若 `d + dist(u to nbr) < cost[nbr]` 則更新相鄰節點到 src 的距離(`cost[nbr] = d + dist(src to nbr)`)
> * 標記 u 為已處理
> 4. 重複第 2. 步驟
>
> 
## 2. Reconstruct Itinerary
<font color="#ee2f56">**Hard**</font>
> You are given a list of flight `tickets` tickets where `tickets[i] = [from_i, to_i]` represent the source airport and the destination airport.
>
> Each `from_i` and `to_i` consists of three uppercase English letters.
>
> Reconstruct the itinerary in order and return it.
>
> All of the tickets belong to someone who originally departed from `"JFK"`. Your objective is to reconstruct the flight path that this person took, assuming each ticket was used exactly once.
>
> If there are multiple valid flight paths, return the lexicographically smallest one.
>
> * For example, the itinerary `["JFK", "SEA"]` has a smaller lexical order than `["JFK", "SFO"]`.
>
> You may assume all the tickets form at least one valid flight path.
### Example 1:
```java
Input: tickets = [["BUF","HOU"],["HOU","SEA"],["JFK","BUF"]]
Output: ["JFK","BUF","HOU","SEA"]
```
### Example 2:
```java
Input: tickets = [["HOU","JFK"],["SEA","JFK"],["JFK","SEA"],["JFK","HOU"]]
Output: ["JFK","HOU","JFK","SEA","JFK"]
```
Explanation: Another possible reconstruction is `["JFK","SEA","JFK","HOU","JFK"]` but it is lexicographically larger.
### Constraints
* `1 <= tickets.length <= 300`
* `from_i != to_i`
### Recommended complexity
* Time complexity: $O(E \cdot \log E)$
* E is the number of tickets(edges)
* Space complexity: $O(E)$
### Solution
#### 1. DFS
(1) 建立 adjacent list
為了保證當有多組解時能夠輸出遞增的順序，所以在建立 adjList 前可以先對 edge 中的各節點進行排序，排序後再建立 adjList
(2) 使用正規的 DFS 步驟即可符合題目要求的走訪所有節點
(3) 因為此圖是 directed graph，所以可能 traversal 的過程可能會導致整張圖無法走完的情況。以下圖為例，當 A -> B 時就會發生無法返回的情況，因為沒有 out-going edges/相鄰點。此時可以使用 bracktracking 返回上一步重新選擇路徑。當某點沒有 out-going edge/相鄰點時就返回上一步。最後以 `res == edges + 1` 判斷是不是所有邊/頂點都已經走過。
```python=
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
# build sorted adjList
adjList = collections.defaultdict(list)
tickets.sort()
for src, dst in tickets:
adjList[src].append(dst)
res = ["JFK"]
def dfs(src):
if len(res) == len(tickets) + 1:
return True
# not have out-going edges
if not adjList[src]:
return False
temp = list(adjList[src])
for i, dst in enumerate(temp):
adjList[src].pop(i)
res.append(dst)
if dfs(dst):
return True
res.pop()
adjList[src].insert(i, dst)
return False
dfs("JFK")
return res
```
但此方法的時間/空間複雜度為 $O(E \cdot V)$
## 3. Min Cost to Connect All Point
<font color="#ffbb00">**Medium**</font>
> You are given a 2-D integer array `points`, where `points[i] = [xi, yi]`. Each `points[i]` represents a distinct point on a 2-D plane.
>
> The cost of connecting two points `[xi, yi]` and `[xj, yj]` is the **manhattan distance** between the two points, i.e. `|xi - xj| + |yi - yj|`.
>
> Return the minimum cost to connect all points together, such that there exists exactly one path between each pair of points.
### Example 1:
```java
Input: points = [[0,0],[2,2],[3,3],[2,4],[4,2]]
Output: 10
```
### Constraints
* `1 <= points.length <= 1000`
* `-1000 <= xi, yi <= 1000`
### Recommended complexity
* Time complexity: better than $O(n^2 \cdot \log n)$
* Space complexity: better than $O(n^2)$
### Solution
題目有給定節點與任意兩節點之間的距離，目的要建立一個連接所有節點且最小 cost 的圖，此即為最小生成樹(Minimum Spanning Tree, MST)。
(1) 建立 adjacent list
將題目給定的點座標編號(0 to n-1)並計算兩兩間的距離(weight)後建立 adjList。AdjList 中每個點都可以與其他的頂點相鄰，且相鄰頂點的儲存方式除了紀錄節點編號以及 undirected graph 的儲存外，還要紀錄兩兩之間的距離權重(`(distance, node)`)，這會用掉 $O(n^2)$ 的空間。
(2) Prime's algorithm
仿照正規 Prime's algorithm 的方式走訪，並在過程中隨時記錄當前的權重和(`cost`)，直到所有節點都拜訪過(`len(visited) == n`)隨即結束。
```python=
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
# build adjList
n = len(points)
adjList = collections.defaultdict(list)
for i in range(n):
xi, yi = points[i]
for j in range(i+1, n):
xj, yj = points[j]
distance = abs(xi - xj) + abs(yi - yj)
adjList[i].append((distance, j)) # (distance, node)
adjList[j].append((distance, i)) # undirected graph
visited = set()
minHeap = []
cost = 0
minHeap.append((0, 0)) # (distance, node)
while len(visited) != n:
dist, node = heapq.heappop(minHeap)
if node in visited:
continue
# update cost
visited.add(node)
cost += dist
# bfs
for nbrDist, nbr in adjList[node]:
if nbr in visited:
continue
heapq.heappush(minHeap, (nbrDist, nbr))
return cost
```
> [!Note] **Prime's algorithm**
> * Prime's algorithm 是一種基於 greedy algorithm 的演算法，旨在建立一個最小生成樹(Minimum Spanning Tree, MST)
> * 給定一個 undirected, connected & weight graph，從中挑選某幾個邊建立一個具有最小 weight sum 的 tree，稱為最小生成樹(MST)
> * Implement
> * Data structure:
> * 使用一個 hash set 儲存已走過的節點，避免重複走訪而形成 cycle
> * 每次透過 minimum heap 取出最小 weight 的路徑
> * Step-by-step: 類似 BFS 的走訪順序
> 1. 從任意點開始作為起點，執行 BFS
> 2. 從 minHeap 中 pop 出一個最小距離的節點
> * 若該節點沒有走過則執行 3.
> * 若該節點走過則繼續取其他節點
> 3. 將此節點加入到 hash set 中建立 MST，並把此節點的相鄰節點與權重全部 push 到 minHeap 中
> 4. 重回第 2. 直到所有節點都走訪過
> * MST 的建立有兩種方式
> * 從一個 cycle graph 中建構出最小 weight sum 的 tree (如 [Reference](https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/) 中的例子)
> * 給定一些節點與邊長，建立連接這些節點與邊長且最小 weight sum 的 tree (如此題)
> * Reference: [Prime's Algorithm for Minimum Spanning Tree](https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/)
## 4. Swin In Rising Water
<font color="#ee2f56">**Hard**</font>
> You are given a square 2-D matrix of distinct integers `grid` where each integer `grid[i][j]` represents the elevation at position `(i, j)`.
>
> Rain starts to fall at time = `0`, which causes the water level to rise. At time `t`, the water level across the entire grid is `t`.
>
> You may swim either horizontally or vertically in the grid between two adjacent squares if the original elevation of both squares is less than or equal to the water level at time `t`.
>
> Starting from the top left square `(0, 0)`, return the minimum amount of time it will take until it is possible to reach the bottom right square `(n - 1, n - 1)`.
### Example 1:
```java
Input: grid = [[0,1],[2,3]]
Output: 3
```
Explanation: For a path to exist to the bottom right square `grid[1][1]` the water elevation must be at least `3`. At time `t = 3`, the water level is `3`.
### Example 2:
```java
Input: grid = [
[0,1,2,10],
[9,14,4,13],
[12,3,8,15],
[11,5,7,6]]
]
Output: 8
```
Explanation: The water level must be at least `8` to reach the bottom right square. The path is `[0, 1, 2, 4, 8, 7, 6]`.
### Constraints
* `grid.length == grid[i].length`
* `1 <= grid.length <= 50`
* `0 <= grid[i][j] <= n^2`
### Recommended complexity
* Time complexity: $O(n^2 \cdot \log n)$
* n is the number of rows or columns of the square matrix
* Space complexity: $O(n^2)$
### Solution
假設某條從起點到終點的路徑，此路徑上的最高水位表示表示這條路徑所需要等待的時間，題目需要回傳走到終點的最小時間，表示我們需要找到所有可能路徑中的最小值(最小水位)。由此可知此題是一種最短路徑問題(shortest path problem)，因為權重都是非負數值，所以可使用 Dijkstra’s Algorithm。
在 Dijkstra’s Algorithm 中使用 minHeap 紀錄距離最近(海拔最低)的數值，並搭配該點的位置 `(r, c)` 一併紀錄。每個方向的迭代過程中會選擇最低的海拔高度方向走訪，並將海拔與位置儲存到 minHeap，此時應該紀錄的是目前該路徑上的最高海拔(比較當前最高海拔與下一個位置的海拔並取最大，`heapq.heappush(minHeap, (max(h, grid[newR][newC]), newR, newC))`)，而不是單純紀錄/儲存下一個位置的海拔位置。
```python=
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
visited = set()
minHeap = [(grid[0][0], 0, 0)] # height, row, col
directions = [(1, 0), (-1, 0), (0, -1), (0, 1)] # up, bottom, left, right
while minHeap:
h, r, c = heapq.heappop(minHeap)
if r == rows - 1 and c == cols - 1:
return h
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):
continue
visited.add((newR, newC))
heapq.heappush(minHeap, (max(h, grid[newR][newC]), newR, newC))
```
## 5. Alien Dictionary
<font color="#ee2f56">**Hard**</font>
> There is a foreign language which uses the latin alphabet, but the order among letters is *not* "a", "b", "c" ... "z" as in English.
>
> You receive a list of non-empty strings `words` from the dictionary, where the words are **sorted lexicographically** based on the rules of this new language.
>
> Derive the order of letters in this language. If the order is invalid, return an empty string. If there are multiple valid order of letters, return any of them.
>
> A string `a` is lexicographically smaller than a string `b` if either of the following is true:
>
> * The first letter where they differ is smaller in `a` than in `b`.
> * There is no index `i` such that `a[i] != b[i]` and `a.length < b.length`.
### Example 1:
```java
Input: ["z","o"]
Output: "zo"
```
Explanation: From "z" and "o", we know 'z' < 'o', so return "zo".
### Example 2:
```java
Input: ["hrn","hrf","er","enn","rfnn"]
Output: "hernf"
```
Explanation:
* from "hrn" and "hrf", we know 'n' < 'f'
* from "hrf" and "er", we know 'h' < 'e'
* from "er" and "enn", we know get 'r' < 'n'
* from "enn" and "rfnn" we know 'e'<'r'
* so one possibile solution is "hernf"
### Constraints
* The input `words` will contain characters only from lowercase `'a'` to `'z'`.
* `1 <= words.length <= 100`
* ` <= words[i].length <= 100`
### Recommended complexity
* Time complexity: $O(N + V + E)$
* N is the sum of the length of all the strings
* V is the number of unique characters(vertices)
* E is the number of edges
* Space complexity: $O(V + E)$
### Solution
將題目給定的字串可以歸納出一個 directed acyclic graph (DAG)，以 Example 2 中的 `["hrn","hrf","er","enn","rfnn"]` 為例，因為題目本身已經依照順序排好，所以可以兩兩做比較
* `hrn < hrf`: n < f
* `hef < er`: h < e
* `er < enn`: r < n
* `enn < efnn`: n < f
由以上結果可以得到兩個 DAG 如下
```
DAG 1: r -> n -> f
DAG 2: h < e
```
我們的目的是根據這些 DAG 找到每個圖中的節點的先後順序關係，因此可以使用拓樸排序(topological sort)，並以後序(postorder)走訪的 DFS 來模擬拓樸排序。
(1) 建立 adjacent list
如果上述的手動操作，透過兩兩一組的比較建立任意兩字母之間的相鄰關係。為了避免重複添加字母(如上述的 n < f)，可以使用 hash set 的方式建立每個節點的相鄰串列。以上述舉例的 adjList 如下
```
{'r': (n,),
'n': (f,),
'f': (),
'h': (e,),
'e': (),
}
```
在建立 adjList 時要排除不合理的輸出。根據題意，不合理的排序情況會有 2 種條件
* 第 1 個單字的長度 > 第 2 個單字
* 第 1 個單字的前綴(prefix)字母 = 第 2 個單字的前綴(prefix)字母
例如 `["lafdy", laf]` 就是不合理的輸入排序。
(2) 拓樸排序
在 DAG 中可以用 postorder 的 DFS 模擬拓樸排序，在拜訪節點時需要不斷走訪直到所有相鄰節點都走過/沒有相鄰節點，再把該點加入到 stack 之中。所以每個節點會有 3 種狀況
* 走過且 push 到 stack 中
* 走過
* 沒走過
如果某節點已經走訪過又再次走訪，表示此圖有 cycle，直接回傳 False
(3) 輸出
因為是用 postorder DFS 在 DAG 中模擬拓樸排序，所以最後的輸出 `res` 與真正的拓樸排序順序剛好顛倒(最先 push 的節點是順序最大的)，需要做一個反轉順序的動作。
```python=
class Solution:
def foreignDictionary(self, words: List[str]) -> str:
# build adjList
adjList = {}
for word in words:
for ch in word:
adjList[ch] = set()
# build directed edges
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
minLen = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
return ""
for j in range(minLen):
if w1[j] != w2[j]:
adjList[w1[j]].add(w2[j])
break
# dfs
visited = {} # True -> pass through, False -> done it, None -> not visited
res = []
def dfs(ch):
# if in visited, return its status
if ch in visited:
return visited[ch]
# if not in visted, go through and record
visited[ch] = True
# go through every neighbor
for nbr in adjList[ch]:
if dfs(nbr):
return True # detect cycle
# after go through every neighbor, add this node to res
visited[ch] = False
res.append(ch)
for ch in adjList.keys():
if dfs(ch):
return ""
res.reverse()
return "".join(res)
```
## 6. Cheapest Flights Within K Stops
<font color="#ffbb00">**Medium**</font>
> There are `n` airports, labeled from `0` to `n - 1`, which are connected by some flights. You are given an array `flights` where `flights[i] = [from_i, to_i, price_i]` represents a one-way flight from airport `from_i` to airport `to_i` with cost `price_i`. You may assume there are no duplicate flights and no flights from an airport to itself.
>
> You are also given three integers src, dst, and k where:
>
> * `src` is the starting airport
> * `dst` is the destination airport
> * `src != dst`
> * `k` is the maximum number of stops you can make (not including `src` and `dst`)
>
> Return **the cheapest price** from `src` to `dst` with at most `k` stops, or return `-1` if it is impossible.
### Example 1:
```java
Input: n = 4, flights = [[0,1,200],[1,2,100],[1,3,300],[2,3,100]], src = 0, dst = 3, k = 1
Output: 500
```
Explanation:
The optimal path with at most 1 stop from airport 0 to 3 is shown in red, with total cost `200 + 300 = 500`.
Note that the path `[0 -> 1 -> 2 -> 3]` costs only 400, and thus is cheaper, but it requires 2 stops, which is more than k.
### Example 2:
```java
Input: n = 3, flights = [[1,0,100],[1,2,200],[0,2,100]], src = 1, dst = 2, k = 1
Output: 200
```
Explanation:
The optimal path with at most 1 stop from airport 1 to 2 is shown in red and has cost `200`.
### Constraints
* `1 <= n <= 100`
* `fromi != toi`
* `1 <= pricei <= 1000`
* `0 <= src, dst, k < n`
### Recommended complexity
* Time complexity: better than $O(n + (m \times k))$
* Space complexity: better than $O(n)$
* n is the number of cities
* m is the number of flights
* k is the number of stops
### Solution
同樣是一個最短路徑問題(shortest path problem)，理論上可用 Dijkstra algorithm，但因為多了一個限制是最多停留 k 個節點，表示最多(at most)可以使用 k+1 個邊，符合 Bellman Ford algorithm 的使用前提。
```python=
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
price = [float("inf")] * n
price[src] = 0
for i in range(k + 1):
temp = price.copy()
for s, d, p in flights:
if price[s] == float("inf"):
continue
if price[s] + p < temp[d]:
temp[d] = price[s] + p
price = temp
return -1 if price[dst] == float("inf") else price[dst]
```
Sign in with Wallet
Connect another wallet