解題說明
Loud and Rich
題目描述： 有 n 個人，richer[i] = [ai, bi] 表示 ai 比 bi 更有錢。quiet[i] 表示第 i 個人的安靜程度（數值越小越安靜）。對於每個人 x，找出所有比 x 有錢（含 x 自己）的人中，最安靜的那個人。
解題思路：
- 建圖 + DFS/拓撲排序：將「有錢」的關係建成有向圖。如果 a 比 b 有錢，建邊 b → a（表示 b 要考慮 a）。
- 對每個人 x，DFS 探索所有比 x 有錢的人（包括間接的），在這些人中找到 quiet 值最小的人。
- 記憶化：如果 x 的答案已經計算過，直接返回，避免重複計算。
- 遞迴關係：answer[x] = argmin(quiet[y]) for y in {x} ∪ {所有比 x 有錢的人的 answer}。
C++ 解法
複雜度分析
時間複雜度：O(n + E) — n 為人數，E 為 richer 關係數量。每個節點和邊只處理一次
空間複雜度：O(n + E) — 圖的鄰接表和遞迴堆疊
虛擬碼
1. Build directed graph: for each (a, b) in richer, add edge b -> a
2. Initialize answer array with -1 (unvisited)
3. For each person i (0 to n-1):
a. Call DFS(i)
4. DFS(node):
a. If ans[node] != -1, return (already computed)
b. Set ans[node] = node (self is the quietest so far)
c. For each richer neighbor next:
- DFS(next)
- If quiet[ans[next]] < quiet[ans[node]]:
- ans[node] = ans[next]
5. Return answer array其他解法
-
拓撲排序 + BFS：先計算每個節點的入度，從入度為 0 的節點（最有錢的人）開始 BFS。處理時將答案傳播到比自己窮的人。這避免了遞迴，適合擔心遞迴深度的情況。
-
暴力 DFS（無記憶化）：對每個人分別做一次完整的 DFS。時間複雜度 O(n*(n+E))，在人數和關係多時會超時，但代碼最簡單。
延伸思考
- 如果「有錢」的關係可能有環（即資料有矛盾），你會怎麼處理？
- 如果我們要找的是所有比自己窮的人中最吵的那個呢？
- 能否在線（online）地回答查詢，即新增有錢關係後快速更新答案？