P3504. 广播服务器

解题思路

本题和 省份数量 不能说毫无联系，只能说一模一样。

解法一：BFS

使用 广度优先搜索 遍历所有节点，每遇到一个未被访问的节点，就将其加入队列，并标记为已访问。然后依次取出队列中的节点，遍历其所有相邻节点，若相邻节点未被访问且存在连接，则将其加入队列并标记。每启动一次 BFS，就说明找到了一个 连通分量，最终统计启动 BFS 的次数即为答案。

关键步骤： 1. 初始化一个 访问数组 visited，长度等于节点数，初始值均为 False。 2. 遍历所有节点，若当前节点未被访问，则计数器加一，并以其为起点执行 BFS。 3. BFS 过程中，使用队列存储待访问节点，并不断将相邻且未访问的节点入队。 4. 遍历结束后，计数器的值即为 连通分量数。

复杂度分析 设 N 为服务器的台数，即连接矩阵的边长。答案是无向图的连通分量个数：每个连通分量只需向其中任意一台服务器发送广播。

• 时间：读入 N × N 矩阵是 O(N^2)。BFS 中每台服务器由 checkList 保证只入队一次，每次出队都要扫描矩阵的一整行（N 个候选邻居）判断连通，所以搜索部分累计也是 O(N^2)。总时间复杂度为 O(N^2)。
• 空间：连接矩阵占 O(N^2)，是主要开销；checkList 和队列各占 O(N)。

边界与注意事项

• 题面规定 matrix[i][i] = 1（每台服务器与自身直接连接），代码在扩展邻居时用 x != y 跳过对角线，避免把自己当作新邻居处理。
• 输入没有单独给出 N：代码先读第一行、按空格切分，用首行元素个数确定 N，再继续读剩余的 N-1 行，解析输入时要与这个格式对上。
• 两个极端情形可用来自查：若除对角线外矩阵全为 0（服务器之间没有任何直接连接），每台服务器自成一个连通分量，答案为 N；若整个集群连通，答案为 1；N = 1 时只有一台服务器，答案也是 1。