华为OD机试“发广播”题解：DFS、BFS、并查集求连通分量

如果你最近在准备华为OD机试，刷题笔记里大概率会遇到“发广播”这道题。它属于图论入门里的“连通分量”题型，题干看着像网络通信题，其实剥开外壳之后核心就是一件事：给定一张无向图，数一数图中有多少个彼此不连通的子图。这道题在华为OD机试C卷中出现频率不低，难度介于第一题和第二题之间，属于“背下套路就能满分”的类型。但也正因为简单，很多人反而在读取输入和边界条件的细节上丢分。这篇文章我会把DFS、BFS、并查集三种主流解法全部讲透，附上机试常用的核心代码写法和自测用例，适合所有正在刷OD题库、想稳拿图论基础分的读者。

1. 题目到底在考什么

1.1 先还原一道典型题目

很多版本的题目描述都差不多，常见的说法是这样：某网络中一共有N个网络节点，编号从0到N-1，用一个N行N列的矩阵Net表示节点之间的连接关系。Net[i][j]等于1，表示节点i和节点j之间可以直接通信；等于0表示不能直接通信。矩阵是对称的，对角线上的值通常是1，因为每个节点理论上可以跟自己通信。现在需要从部分节点主动发出广播，收到广播的节点会立刻把广播转发给所有能直接通信的邻居。问：至少需要从几个节点发出广播，才能保证所有节点最终都能收到广播。

输入输出格式一般这样：

4 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1

期望输出是2。原因很简单：节点0和节点1直接相连，节点1又和节点2直接相连，所以0、1、2这3台可以通过转发相互通信，只要从其中任意一台发一次广播，另外两台就能收到。节点3和谁都不直接相连，必须单独给它发一次。所以总的最少广播次数是2。

1.2 核心考点：数连通分量

这道题的名字叫“发广播”，但它本质上和“广播”这个动作没有太大关系。你需要抓住一个关键点：如果若干节点可以通过直接连接关系间接到达彼此，那么它们就属于同一个“连通分量”。在一个连通分量内部，只要选定一个源头发广播，扩散过程会自动覆盖分量里的所有节点。因此，最少需要发起广播的次数，就等于整个网络中有多少个独立的连通分量。

我习惯用一个生活化的类比来解释：想象公司通知要传达给N个微信群，如果一个群里有人看到了通知并转发，那么全群都会知道；如果群与群之间没有任何重叠成员，那每个群都必须单独发一次。这里需要单独发消息的群数量，就是互不连通的“群分量”数量。

面试官爱出这道题，是因为它同时考察了两件事：第一，能不能把实际问题抽象成图模型；第二，会不会用最基本的图遍历算法来统计连通分量。这属于算法基础能力，也是后续做更复杂图论题的铺垫。

2. 解法一：深度优先搜索（DFS）

2.1 思路与状态设计

DFS的思路非常直白。准备一个boolean数组visited，长度是N，用来记录每个节点有没有被访问过。然后从编号0开始遍历所有节点：

• 如果当前节点没有被访问过，说明它属于一个新的连通分量，计数器加1；
• 从这个节点出发，递归访问所有能直接到达的邻居节点；
• 每访问到一个邻居，就继续深入它的邻居，直到这一整块连通区域里的节点都被标记完。
• 接着看下一个还没被访问的节点，继续重复这个过程。

这里最核心的“为什么能这样写”在于：一个连通分量里，总有一个节点在外层循环中第一次被碰到。它的所有“同伴”都会在这次递归里被访问并标记。等到外层循环继续往后走，看到这些已经被标记的节点时，会直接跳过，不会重复计数。这就保证了计数一次对应一个连通分量。

2.2 可以提交的Java代码

如果是ACM模式，需要自己处理输入输出，典型写法如下：

import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static int n; static int[][] net; static boolean[] visited; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine().trim()); net = new int[n][n]; visited = new boolean[n]; for (int i = 0; i < n; i++) { String[] parts = br.readLine().trim().split("\\s+"); for (int j = 0; j < n; j++) { net[i][j] = Integer.parseInt(parts[j]); } } int count = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { count++; dfs(i); } } System.out.println(count); } static void dfs(int cur) { visited[cur] = true; for (int next = 0; next < n; next++) { if (net[cur][next] == 1 && !visited[next]) { dfs(next); } } } }

如果是核心代码模式，通常只要求实现一个方法，比如：

public int broadcast(int[][] net) { int n = net.length; boolean[] visited = new boolean[n]; int count = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { count++; dfsByIndex(net, i, visited); } } return count; } private void dfsByIndex(int[][] net, int cur, boolean[] visited) { visited[cur] = true; for (int next = 0; next < net.length; next++) { if (net[cur][next] == 1 && !visited[next]) { dfsByIndex(net, next, visited); } } }

递归写法在代码量上是最少的，逻辑也最贴近“顺着连接一路走到底”的直觉，适合考场上快速完成。

2.3 递归深度的坑与显式栈写法

我做这道题的时候，第一次没多想就用了递归。如果题目把N限制在100以内，递归完全没问题。但万一你遇到变体题把N放大到好几千，递归深度可能会比较危险，考场环境有时候对递归调用栈并不友好。这时候可以用显式栈替代递归，逻辑完全一致：

static void dfsStack(int start) { Deque<Integer> stack = new ArrayDeque<>(); stack.push(start); visited[start] = true; while (!stack.isEmpty()) { int cur = stack.pop(); for (int next = 0; next < n; next++) { if (net[cur][next] == 1 && !visited[next]) { visited[next] = true; stack.push(next); } } } }

如果按系统提示执行，这段代码用一个ArrayDeque模拟了系统函数调用栈，好处是不用担心递归层数过深，缺点是需要自己维护遍历顺序。对于本题场景，DFS和显式栈版本的时间复杂度都是O(N^2)，空间复杂度都是O(N)，实际差别很小。

3. 解法二：广度优先搜索（BFS）

3.1 换一个思路：逐层扩散

BFS解法和DFS在整体框架上几乎一样，唯一的区别是：DFS沿着一条路径深入到底再回头，BFS则使用队列，先把当前节点的所有邻居都入队，再一层一层往外扩散。

“发广播”这个场景天然适合BFS，因为广播的真实行为就是逐层传播：第一个节点收到广播，它把所有邻居拉进群；邻居们再拉自己的邻居，就像水面上的波纹一圈圈荡开。用BFS模拟这个过程，语义上非常贴切。

3.2 完整Java代码

下面这段是ACM模式下用BFS实现的完整代码：

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; public class Main { static int n; static int[][] net; static boolean[] visited; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine().trim()); net = new int[n][n]; visited = new boolean[n]; for (int i = 0; i < n; i++) { String[] parts = br.readLine().trim().split("\\s+"); for (int j = 0; j < n; j++) { net[i][j] = Integer.parseInt(parts[j]); } } int count = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { count++; bfs(i); } } System.out.println(count); } static void bfs(int start) { Queue<Integer> queue = new LinkedList<>(); queue.offer(start); visited[start] = true; while (!queue.isEmpty()) { int cur = queue.poll(); for (int next = 0; next < n; next++) { if (net[cur][next] == 1 && !visited[next]) { visited[next] = true; queue.offer(next); } } } } }

注意一个细节：在BFS里，把邻居节点入队的同时就要立刻标记visited，不能等它出队的时候再标记。如果入队时不标记，同一个节点可能被多个邻居重复加入队列，既增加无效操作，也可能导致死循环。这也是我在实际写代码时踩过的坑。

3.3 BFS和DFS怎么选

从考试拿分的角度看，DFS代码更短，出错概率更低，适合作为首选。BFS的优势在于它天然避免递归栈过深的问题，而且遇到“求从某个节点发出的广播能覆盖多少节点”这类变体时，BFS可以顺带计算层数或传播距离。并查集则适合后续需要动态添加连接关系的场景。

如果你只打算掌握两种，我建议DFS和BFS都练熟。因为它们只是遍历顺序不同，框架几乎一样，练会了以后遇到二维网格版的“岛屿数量”也能很快迁移。

4. 解法三：并查集（Union-Find）

4.1 并查集为什么也适合这个场景

并查集是解决连通性问题的经典结构，它的核心能力是快速判断两个元素是否属于同一个集合，以及快速合并两个集合。对于本题，我们可以遍历邻接矩阵，遇到值为1的位置就把两个节点所属的集合合并，最后统计有多少个不同的集合。

这种思路和DFS/BFS的区别在于：DFS/BFS是“从某个点开始向外扫”，并查集是“把所有连接关系两两合并”，最后统一统计。在代码实现上，并查集不需要递归遍历整张图，也不需要用visited数组，而是维护一个parent数组。

4.2 路径压缩与按秩合并

并查集的代码不算复杂，关键在两个优化：路径压缩和按秩合并。路径压缩是指find操作在找到根节点的过程中，把沿途经过的节点直接挂到根节点下面，这样下次查找几乎是O(1)。按秩合并是指在union操作中，优先把树高较低的根挂到树高较高的根下面，避免树长得太高。

完整实现如下：

import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static int[] parent; static int[] rank; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); int[][] net = new int[n][n]; for (int i = 0; i < n; i++) { String[] parts = br.readLine().trim().split("\\s+"); for (int j = 0; j < n; j++) { net[i][j] = Integer.parseInt(parts[j]); } } parent = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 0; } // 无向图只用遍历上三角，避免重复合并 for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (net[i][j] == 1) { union(i, j); } } } int count = 0; for (int i = 0; i < n; i++) { if (find(i) == i) { count++; } } System.out.println(count); } static int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // 路径压缩 } return parent[x]; } static void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) { return; } if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; } } }

这里遍历矩阵时只遍历上三角，也就是j从i+1开始。因为这是一个无向图，net[i][j]和net[j][i]是同一个连接关系，只合并一次就够了。如果不注意这个细节，虽然不会算错，但白白多执行一遍合并操作。统计根节点个数时，find(i) == i就表示节点i是它所在集合的根，根的个数就是连通分量个数。

4.3 三种解法横向对比

时间复杂度上，三种解法都躲不开扫描整个邻接矩阵的O(N^2)开销，所以差距不大。并查集的代码虽然稍微长一点，但它天然适合“动态加边”的场景，如果题目后续要求新增连接后重新判断连通性，并查集改造成本最低。

5. 机试实战细节：输入输出与得分技巧

5.1 先搞清楚是ACM模式还是核心代码模式

华为OD机试不同批次和不同题目卷的代码提交方式不完全一样。有些场次是ACM模式，需要选手自己写Main类、自己处理输入输出；有些场次是核心代码模式，系统给好类名和方法签名，只需要在方法体里填空。两种模式在备考时都要练。我推荐的策略是：平时刷题一律按ACM模式自己处理输入输出，这样核心代码模式自然也会，反过来只练核心代码模式，遇到ACM模式就会手足无措。

5.2 读取输入的兼容写法

“发广播”这类题的邻接矩阵输入有个烦人的地方：有的题目每行数字之间有空格，比如“1 0 1”，有的题目直接给“101”，中间没有空格。如果只写其中一种解析方式，遇到另一种格式就崩了。我在实际刷题时总结了一个兼容两种格式的读取写法：

for (int i = 0; i < n; i++) { String line = br.readLine().trim(); String[] parts = line.split("\\s+"); if (parts.length == n) { // 有空格的情况 for (int j = 0; j < n; j++) { net[i][j] = Integer.parseInt(parts[j]); } } else { // 无空格的情况，直接按字符读 for (int j = 0; j < n; j++) { net[i][j] = line.charAt(j) - '0'; } } }

先用split按空格切分，如果切出来正好是n份，说明输入里带了空格；否则就按单字符读取。这一个细节能在考场上帮你省下不少调试时间，也是我觉得最实用的经验之一。

5.3 最容易丢分的三个细节

第一，对角线是0还是1不影响判断。很多题目说“对角线为1”，但也有题目给的是0。判断连通关系时只看i和j不一样的位置即可，或者干脆不区分，因为count统计的是连通分量数量，不受对角线影响。第二，visited数组要记得初始化。Java里boolean默认是false，不初始化也能用，但如果你用int数组，一定要显式初始化为0。第三，在BFS里入队时就标记visited，而不是出队时标记。前面已经说过，这个坑会导致重复入队甚至逻辑错误。

我还想提醒一点：如果题目明确说节点编号从1开始，读入后最好把所有循环都统一成0-based，否则一会从0开始一会从1开始，很容易在边界上翻车。

5.4 自测用例与边界情况

这些用例是提交代码前必跑的。很多错误不是算法思路错了，而是边界情况没覆盖到。

6. 由“发广播”引申：连通分量题的识别与迁移

6.1 看到什么描述能想到连通分量

我把这类题的常见信号词整理了一下，遇到这些特征就可以优先往“连通分量”方向想：出现了N个节点或N个城市、用矩阵表示连接关系、两个对象之间可以直接通信/连接/认识、信息会自动传播或扩散、题目问“最少需要几个源头/几次操作”。经典的变体包括LeetCode 547“省份数量”、LeetCode 200“岛屿数量”、LeetCode 684“冗余连接”等。

判断方法很简单：把每个对象看成图节点，把“直接关系”看成边，一个分量就是一个需要单独处理的整体。如果题目问的是“最少需要几个起点”，基本上就是在问分量的个数。

6.2 从这道题到更多变体

掌握了这道题的解法后，可以顺带解决一批变体。比如把题目改成“如果发广播一次只能覆盖整个连通分量，但是我们可以任意选择发广播的起点，问最少需要几次”，本质完全相同。再比如“求最少加几条边能让整个网络变成完全连通”，答案就是当前连通分量数量减1，因为每加一条边最多能把两个连通分量合并成一个。

另一个方向是二维网格版的连通问题，比如一个m行n列的网格，1表示陆地，0表示海水，问有多少块陆地。这时候DFS、BFS、并查集依然适用，只是邻居的判断从“遍历一整行”变成“上下左右四个方向”。框架完全一样，代码稍微调整就行。

我个人在实际操作中的体会是：刷题时不要只满足于提交通过，多花十分钟把三种方法都写一遍，收益远大于多刷三道同类型的题。因为“发广播”这道题虽然简单，但它把图论里最基础也最重要的遍历思想和并查集都串起来了，三种解法都练熟了，再遇到任何连通分量变体题，思路都会非常清晰。