剛花了點時間來AC這題。
原本採用SCC的Tarjan algorithm，但發覺和題意不太符合。
因為我不需要找強連結的根。
後來採用的是
資料結構，
a.一整數陣列用來記錄最後有幾個團。
b.每一節點2個整數變數，變數1第幾個節點，變數2地幾個set，
c.另有每一節點的有向邊集合。
d.函數內為類SPFA的隊列。
algo:
1.初始化給n個炸彈標記1 ~ N，變數1和變數2值一樣。
2.loop，如果該節點的變數1和變數2相等，進入3.，否則5.
3.pop出來隊列頭並且引爆其他炸彈，若其他炸彈的尚未在隊列裡，
且其他炸彈的變數2不等於此節點的變數2，
則更新其他炸彈的變數2等於此節點的變數2，將其他炸彈放進隊列。
4.隊列不為空重複3.
5.loop所有節點，標記陣列[變數2的值] = 1。
6.loop整數陣列找出有幾個團(有幾個1)。
7.結束。
※ 引述《scwg ( )》之銘言：
: ※ 引述《iamnotgm (伽藍之黑)》之銘言：
: : 問題是這樣的
: : 座標平面上有幾個炸彈
: : 每個炸彈引爆時會炸出一個正方形的範圍
: : 任何在這個範圍內的其他炸彈會連鎖反應一起炸
: : 給定N個炸彈的位置和爆炸範圍後
: : 求點燃最少的炸彈把所有的炸彈炸光
: : 我的解法是先找出每一顆炸彈可以炸到誰
: : 做出一張graph後找出不會被其他人炸到的炸彈先炸
: : 炸完後剩下來還沒引爆的炸彈應該就是存在於環上
: : 先假定引爆A炸彈
: : 之後如果再引爆B炸彈發現他會點燃A炸彈就把A炸彈拿掉
: : 直到所有的炸彈都被主動或被其他炸彈引爆
: : 這個樣子的解法會wrong answer
: : 但是我想不出來有什麼樣的case是我的演算法沒考慮到的
: 試試看
: 3
: 6 4 1
: 4 4 4
: 8 4 4
: 根據你第二步選出 A 炸彈的方法, 可能要把輸入順序調換一下.
: 無論如何, 這個測資長這樣
: _______________
: | | _ | |
: | B |A| C |
: |____|_____|____|
: 也就是 B, C 會互相引爆, 也都會引爆 A, 但是 A 爆炸不會有連鎖反應
: 因此問題出在這一句:
: 炸完後剩下來還沒引爆的炸彈應該就是存在於環上
: 應該要修正為:
: 炸完後剩下來還沒引爆的炸彈應該就是存在於環上,
: 或者會被環上任一個炸彈的連鎖反應引爆
: 因此第二步要確定引爆的 A 炸彈
: 1. 確實在環上
: 不過這樣還不太夠, 考慮下面這個 graph
: C -> A
: ^ ^
: | |
: v v
: D B -> E
: 上面那個條件確保我們不會選到 E, 但是我們仍然可能選到 A 或 B
: (正解為引爆一次, C 或 D, 引爆 A, B, 或 E 都需要兩次以上)
: 因此還需要第二個條件
: 2. 不會被另一個環上任一個炸彈的連鎖反應引爆
: 到這裡有沒有發現第二步和第一步幾乎一模一樣, 只不過把『炸彈』換成『環』?
: (第一步的兩個條件是:
: 1. 確實是一個炸彈
: 2. 不會被另一個炸彈引爆
: )
: 因此我們可以把圖上每個環視為一個大炸彈, 然後數數看有幾個 (大) 炸彈不會
: 被連鎖反應炸到, 需要手動引爆, 就是答案了.
: 這麼一來問題就變成, 要怎麼找出所有的『環』呢?
: 要注意所謂的『環』不一定是一個圈喔!
: A <- B -> D
: | ^ |
: | | |
: +