刚花了点时间来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
: | ^ |
: | | |
: +