根据题目的范围n<=100,可以大胆地设计n^3时间复杂度的算法。我们随意采用一个炸弹作为初始引爆点,题目所给的条件可以知道哪些后续炸弹会被第一个引爆。于是我们将这些后续一定会被引爆的炸弹也放入一个队列。之后队列里只要每弹出一个能被引爆的炸弹,我们就加入后续能被引爆的炸弹(已经引爆过的不算)。于是这就是一个非常直观的BFS。
注意本题的时间复杂度。选取初始引爆炸弹需要o(n)的遍历;之后的队列的维护生成需要o(n);每次我们根据一个已引爆炸弹穷举所有可能被引爆的炸弹,这也需要o(n)。所以总的时间复杂度是o(n^3).