题解：B4309 [蓝桥杯青少年组国赛 2024] 第四题

Bobi2014 · 2025-05-14 20:52:56 · 题解

这是一道 可爱 的 Tarjan 题目。

Update 2025.05.17：感谢 @Yezi_damn 提出的问题，将 < 3 写成 < 2 了。

前置知识

• Tarjan

思路

因为题目中的 T、n、m 都很小，所以我们考虑把棋盘变成图，只需要把相邻 2 个棋子连边即可，接下来我们分类讨论：

• 如果连通块个数已经 > 1 了，那么输出 0。（这一步使用 dfs）
• 如果点数已经 < 3 了，那么输出 -1。（这一步使用特判）
• 如果存在割点，说明只要 1 步就可以把连通块切开，那么输出 1。（这一步使用 Tarjan）
• 否则因为这一步肯定存在大小 > 2 的环，所以输出 2。（这一步使用特判）

时间复杂度 O(T \times n \times m)。