題目描述:
給定 n 個炸彈,每個以 [x, y, r] 表示(圓心座標和爆炸半徑)。引爆一個炸彈後,其爆炸範圍內的其他炸彈會連鎖引爆(被引爆的炸彈也會觸發自己範圍內的其他炸彈)。注意引爆關係是有向的:A 引爆 B 不代表 B 能引爆 A。求引爆一個炸彈能產生的最大連鎖引爆數量。
解題思路:
(i, j),若炸彈 i 的爆炸範圍覆蓋炸彈 j 的圓心(即距離 <= r_i),則建一條有向邊 i -> j。距離計算用平方避免浮點誤差。時間複雜度:O(n^3) — 建圖 O(n^2),對每個起點 BFS 為 O(n + E),共 n 次,最壞情況 E = O(n^2)。
空間複雜度:O(n^2) — 鄰接表儲存有向邊。
1. Build directed graph:
For each pair (i, j):
If distance(bomb_i, bomb_j) <= radius_i:
Add edge i -> j
2. For each bomb i as starting point:
a. Run BFS/DFS from i
b. Count reachable nodes
3. Return maximum countFloyd-Warshall O(n^3):建立可達性矩陣,用傳遞閉包計算每個節點可達的節點數。時間複雜度相同但常數較大。
SCC 縮點 + 拓撲排序:先用 Tarjan 或 Kosaraju 找強連通分量,縮點後在 DAG 上計算最大可達節點數。時間複雜度 O(n^2),但實作複雜度高,對 n <= 100 的限制不必要。