P3497. 精准核酸检测

解题思路

本题让人回想那段岁月..恍若隔世

问题类型与基本思路

非常典型的搜索问题，很容易想到直接套用 DFS / BFS 模板来完成。

图的表示方式

注意所给的无向图是以关联矩阵 mat 来呈现的，即 mat[i][j] == 1 表示 i 和 j 有关联（有接触）。

搜索的起点

另外，需要注意进行搜索的初始节点可能有多个。若：

• 进行 DFS，那么需要多次进行 DFS 入口函数的调用
• 进行 BFS，那么队列的初始状态需要储存多个节点

关键陷阱

注意：本题存在一个非常坑的地方，就是原本已经确诊的人是无需再做核酸检测的，只有连通块中的其他人才需要做检测。

图的表示转换

如果不熟悉关联矩阵，也可以将关联矩阵转化为邻接表来表示。

关联矩阵复习

复习一下无向图关联矩阵的特点：

• mat[i][j] == 1 表示 i 和 j 关联，mat[i][j] == 0 表示 i 和 j 无关
• 对角线一定为 1，即 mat[i][i] == 1 恒成立，因为每一个人总和自己关联
• 关联矩阵一定沿着对角线对称，即 mat[i][j] == mat[j][i]，因为 i 和 j 关联等价于 j 和 i 关联

代码

解法一：DFS

复杂度分析 设 n 为总人数，即关联矩阵的边长。

• 时间：读入 n × n 的关联矩阵本身就需要 O(n^2)。DFS 过程中，checkList 保证每个人最多被真正访问一次，每次访问都要扫描矩阵的一整行（n 个候选邻居），所以搜索部分累计也是 O(n^2)。总时间复杂度为 O(n^2)。
• 空间：关联矩阵占 O(n^2)，是主要开销；checkList 占 O(n)；DFS 递归栈在最坏情况（传播链连成一条链）下深度可达 O(n)。

边界与注意事项

• 确诊病例自己不需要检测：代码里 ans 统计的是搜索中访问到的所有人（包含确诊者本人），最后输出 ans[0] - startList.size() 把确诊人数减掉，漏掉这一步会多算。
• 搜索起点可能有多个：主函数对确诊列表里的每个编号都尝试调用一次 dfs，并用 checkList[i] == 0 判断是否已被之前的搜索覆盖。两个确诊者若处在同一条传播链上，第二次调用会被直接跳过，不会重复统计。
• 输入的确诊编号行和矩阵的每一行都是逗号分隔，代码用 StringTokenizer 按 "," 切分，处理输入时不要按空格切。
• 关联矩阵对角线恒为 1（每个人和自己关联），dfs 里用 j != i 跳过自身，避免把自己当成新的邻居去递归。