最近集中刷华为OD机试真题做到“发广播”这道题的时候我停顿了一下。题目本身不难但第一次做的时候我直接把它理解成了“从一个站点出发最多能覆盖多少站点”样例轻松通过提交却挂了。重新读题才意识到它真正要的答案是整个广播网络里最少需要选几个站点作为初始广播源才能让所有站点都收到广播。翻译成图论语言就是数无向图的连通分量个数。这篇文章想把我的完整思考过程、两种主流写法DFS/BFS 和并查集以及考试场景下输入输出的处理细节都整理出来。对于正在准备华为OD机试尤其是Java方向、C卷ACM模式的朋友可以直接参考。这道题在OD机试里属于“看着简单但容易栽在建模上”的典型既考邻接矩阵遍历又考对连通性概念的理解。平时如果不注意这一类题考场上很容易在第一步就跑偏。1. 题目理解与核心考点1.1 题目场景到底在问什么先给出一个常见的题目版本大家在各种OD题库里看到的“发广播”基本是这个意思N个广播站组成一个广播网用一个 N×N 的矩阵 connection 表示站点之间的相邻关系connection[i][j] 1 表示站点 i 和站点 j 可以直接通信0 表示不能直接通信主对角线 connection[i][i] 也固定为 1。如果从某个站点发出广播信号会沿着所有能通信的路径自动转发最终能传到所有直接或间接连通的站点。问最少需要从多少个站点主动发起广播才能让全网所有站点都收到至少一次广播读完题别急着写代码。这里有一个关键动作把自然语言翻译成数学模型。“信号会沿着所有能通信的路径自动转发”意味着什么意味着只要两个站点之间存在一条直接或间接的路径它们就属于同一个“可互相到达”的整体。这种关系在离散数学里叫等价关系满足自反、对称、传递。整张网会被划分成若干个互不可达的连通块每个连通块内部任意两点都能互相通信块与块之间没有任何路径。那么我们最少需要从几个站点发起广播答案就是连通块的数量。道理很简单每个连通块内部选一个站点发广播信号就能覆盖整个块不同的连通块之间没有路径你在块A里无论怎么发都进不了块B所以每个块都至少要有一个发起源。反过来每个连通块恰好选一个也一定够。因此“发广播”这道题问的其实是给定一个无向图数一数图里有多少个连通分量。这个转化看起来简单但考场上一紧张就可能跑偏。我当时就是把“从一个点出发能访问到多少个点”和“最少需要几个起点”混在一起答案直接变成了最大可达节点数浪费了不少时间。1.2 为什么是连通分量而不是“可达范围”很多人卡在这道题是因为同时想到了两个概念单点可达集合和全局连通分量。这两种问法结果完全不同。如果题目问的是“从第 k 个站点发广播最多能覆盖多少个站点”那就是单源可达的节点数属于图的遍历题用一次 DFS 或 BFS 从指定起点开始统计访问了几个节点就行。但“发广播”问的是“最少需要几个起点才能覆盖全部”这就是全局规划问题。由于一个起点只能覆盖它所在的连通分量所以全局最少起点数就是连通分量个数。如果误当成前者只跑一次 DFS那当然会漏掉很多未覆盖区域。所以做题第一步永远是划重点题目里有没有“最少需要几个源”“所有点都要覆盖到”这种词。有就大概率是连通分量计数而不是单点可达。这个判断能力比背模板重要得多。1.3 解法选型DFS/BFS还是并查集明确了要数连通分量剩下就是实现路径的选择。邻接矩阵版DFS最直观代码量最少二三十行能搞定。对每个未访问节点执行dfs每次进入一个新的未访问节点就把答案加1适合矩阵规模在几百或一千以内的题目。邻接矩阵版并查集先让每个节点自成一派再扫描矩阵中有连接的位置执行合并最后统计还有多少个根。代码稍长但是逻辑非常统一不太依赖递归。邻接表版BFS如果题目输入给的是边列表而不是矩阵用邻接表配合队列更合适。对于OD机试的“发广播”矩阵规模通常不会特别大一般N≤200或N≤1000两种主流写法都能过。如果让我推荐我首选并查集。原因后面会细说一是省去递归不会因为路径太长导致栈溢出二是后面很多变体题比如“最少加几条线能全网互通”可以直接复用同一个并查集三是它更贴近“合并集合”的语义容易排查错误。2. 解法一DFS/BFS 遍历连通分量2.1 套路与模板DFS解法其实就是“染色法”的图版。维护一个 boolean[] visited长度为 N初始全部为 false。外层循环从 0 到 N-1 一次检查每个站点如果当前站点 i 还没被访问说明它属于一个全新的连通分量此时答案 ans 加 1然后以 i 为起点做一次 DFS凡是能从 i 到达的站点全部标记 visited true继续外层循环直到所有站点都已被访问过。这样外层循环每遇到一个“还没被访问过”的节点就必然发现一个新的连通分量。可以把每个连通分量理解为一种颜色DFS就是给整块区域上色外层循环数一数一共用了多少种颜色。BFS写法只是把递归栈换成显式队列本质没有区别。如果担心递归深度或平台对递归栈不友好就优先用BFS。从上到下的思路几乎一样只是把“递归找邻居”变成了“队列循环弹出”。2.2 Java实现含注释import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[][] grid new int[n][n]; for (int i 0; i n; i) { for (int j 0; j n; j) { grid[i][j] sc.nextInt(); } } boolean[] visited new boolean[n]; int ans 0; for (int i 0; i n; i) { if (!visited[i]) { ans; dfs(grid, visited, i, n); } } System.out.println(ans); } private static void dfs(int[][] grid, boolean[] visited, int i, int n) { visited[i] true; for (int j 0; j n; j) { if (grid[i][j] 1 !visited[j]) { dfs(grid, visited, j, n); } } } }这段代码里有几个细节要说明。第一ji的格子不用特殊处理。因为进入dfs时立刻把visited[i]置为 true循环到ji时会因为!visited[j]不成立而跳过不会造成自循环。第二grid[i][j] 1这个判断实际上把矩阵当成了邻接矩阵来用时间复杂度必然达到 O(N²)。N 在 1000 以内没问题但 N 到 5000 甚至更高时就要考虑用邻接表或优化输入。第三如果矩阵不保证对称比如只有grid[i][j] 1但grid[j][i]可能是0这个DFS仍然把它当成无向图的遍历来跑。因为在“广播能原路返回”的语义下路径是双向的只要 i 能到 j我们就认为 j 能到 i。如果题目明确说是单向转发那就要换解法了这点我在第5章会单独说。2.3 BFS版本如果你想用BFS把dfs调用替换成下面这段即可QueueInteger queue new ArrayDeque(); visited[i] true; queue.offer(i); while (!queue.isEmpty()) { int cur queue.poll(); for (int j 0; j n; j) { if (grid[cur][j] 1 !visited[j]) { visited[j] true; queue.offer(j); } } }注意这里有一个新手容易犯的错在queue.offer(j)之前就已经把visited[j]置为 true而不是等 poll 出来再置。原因是避免同一个节点被多个邻居重复入队。如果等出队才标记那么在一个完全图中第一个节点会把 N-1 个邻居都入队第二个节点出队时会再次判断这些邻居是否已访问虽然逻辑对但队列可能膨胀效率变差。刷OJ时尽量做到“入队即标记”这是一个很通用的BFS优化习惯。3. 解法二并查集Union-Find3.1 并查集在做什么并查集很适合这类“元素之间有关系要划分类别”的问题。一句话解释它维护了一个“谁和谁是同一伙”的集合关系支持两种操作——查find和并union。find(x)找到 x 这个元素所在集合的代表元素一般叫根。为了加快速度过程中会做路径压缩让 x 直接指向根。union(x, y)把 x 和 y 所在的两个集合合并成一个。用在“发广播”上初始时每个站点单独成为一个集合也就是说每个站点的根都是自己。然后遍历连接矩阵发现grid[i][j] 1就把 i 和 j 所在集合合并。所有连接处理完之后再统计有多少个集合的根还是自己这个数量就是连通分量数也就是答案。可以打个比方社团招新。一开始每个人都是只有自己的小社团只要两人有关系就把两边社团合并处理完所有关系后数一数还剩多少个独立社团就是最少需要的广播源数量。3.2 Java实现import java.util.Scanner; public class Main { static int[] parent; static int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩 } return parent[x]; } static void union(int a, int b) { int rootA find(a); int rootB find(b); if (rootA ! rootB) { parent[rootB] rootA; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[][] matrix new int[n][n]; for (int i 0; i n; i) { for (int j 0; j n; j) { matrix[i][j] sc.nextInt(); } } parent new int[n]; for (int i 0; i n; i) { parent[i] i; } // 只看上三角避免同一对连接处理两遍 for (int i 0; i n; i) { for (int j i 1; j n; j) { if (matrix[i][j] 1) { union(i, j); } } } int ans 0; for (int i 0; i n; i) { if (parent[i] i) { ans; } } System.out.println(ans); } }这段代码有一个必须强调的点统计根节点之前最好对每个节点都先执行一次find(i)把整棵树的节点都压缩到根下。上面这段代码其实并不一定需要全量find因为路径压缩是递归做的且我们只关心parent[i] i的数量不可能因为压缩不足而多算或少算。但严谨一点可以在统计前加一个 for 循环for (int i 0; i n; i) { find(i); }这样保证所有 parent 都指向最顶层的根。虽然不压缩也能统计对但压缩之后逻辑更清晰也方便你debug时打印parent数组。3.3 两种解法的对比对比项DFS/BFS并查集代码量更少稍微长一点递归风险DFS有风险BFS无无find递归深度受路径压缩控制时间O(N²)O(N²·α(N))α接近常数空间visited O(N)递归栈O(N)parent O(N)扩展性换题目可能要重写加边、动态合并很方便实际做题选哪个都可以。如果实在拿不准我建议先用DFS快速验证思路再把并查集版本也写一遍这样两种套路都练了考场上换着来也不慌。4. OD机试实战输入输出与AC细节4.1 看清是ACM模式还是核心代码模式华为OD机试有两种常见出题方式。一种是“核心代码”模式平台已经帮你把输入解析好只让你实现一个方法方法入参是矩阵返回值是答案。另一种是ACM模式需要自己写public static void main自己读输入、自己输出。现在不少题目两种模式都可能出甚至有同学反映OD更偏ACM模式所以要两手准备。核心代码模式下的函数大概长这样public int minBroadcastSources(int[][] grid, int n) { // 在这里面写DFS或并查集 return ans; }ACM模式就是要写完整程序上面我给的代码就是ACM模式的写法。准备OD机试建议每天至少用ACM模式练三题否则到了考场上可能会在输入解析上卡住反而不如核心代码模式舒服。4.2 矩阵输入的三种姿势第一种Scanner配合nextInt()。代码简单适合 N 较小的情况。如果 N 到 1000矩阵有 100 万个整数Scanner勉强能跑但在平台超时边缘时容易出问题。第二种BufferedReaderStringTokenizer。BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine().trim()); int[][] matrix new int[n][n]; for (int i 0; i n; i) { StringTokenizer st new StringTokenizer(br.readLine()); for (int j 0; j n; j) { matrix[i][j] Integer.parseInt(st.nextToken()); } }这是我个人在OD机试里最推荐的写法读取速度快逻辑也清晰。很多大矩阵TLE其实不是算法问题而是输入方式太慢。第三种有的题把矩阵每行写成连续字符串比如110\n101\n011这时候不能按数字读取要先按行读进来再用charAt(j) - 0转成整数。for (int i 0; i n; i) { String line br.readLine().trim(); for (int j 0; j n; j) { matrix[i][j] line.charAt(j) - 0; } }如果是这种格式题目描述里一定会有提示比如“矩阵元素之间没有空格”。考试时一定要先看样例输入长什么样再决定用哪种解析方式。这个习惯能省掉很多莫名其妙的运行错误。4.3 统计答案前要不要再find一遍前面说过并查集统计根节点的标准做法是int ans 0; for (int i 0; i n; i) { if (find(i) i) { ans; } }这样写等于在统计的同时完成路径压缩最稳。如果只判断parent[i] i大部分时候结果也对但遇到父节点还没完全压平的情况可能让人产生困惑。用find(i)当条件每次都会返回真正的根可靠性和可读性都更好。另外union的时候可以加一个小优化“按大小合并”把小树并入大树避免形成很深的链。对于 N 这么大的矩阵来说路径压缩已经足够不写按大小合并也能过但写成parent[rootB] rootA这种不平衡合并在极端情况下可能导致find的递归链变长。想更稳就加一个size数组。4.4 题目里的“1”到底代表什么还有一个高频坑题目矩阵里的1到底代表“连接”还是“可达”如果是“连接”那么只有直接相邻的站点能一步到达我们才把它合并如果是“可达”那可能已经包含了间接关系这时你根本不用遍历数数就行因为可达矩阵的连通分量可以直接通过“闭包”来算。OD题库里常见的是连接矩阵也就是邻接矩阵需要我们用图算法去推导间接关系。遇到题目时先看题目定义有没有“直接”“相邻”“一步可达”这类词。4.5 控制复杂度别在遍历时重复合并在并查集写法里如果矩阵是对称的i和j的连接关系会在matrix[i][j]和matrix[j][i]各出现一次。我们只遍历j i 1到 N-1也就是上三角能省掉一半无效合并。如果你是见一个合并一个把整个矩阵都扫了也没问题因为union里rootA ! rootB的判断会过滤掉重复合并但白白多做一些find。N 小无所谓N 大时还是要养成“无向图只看上三角”的习惯。5. 变体与举一反三5.1 输入变成边列表有些题不直接给矩阵而是给 N 和 M 条边。比如输入 N 和 M接下来 M 行每行两个整数 u v表示站点 u 和 v 可以直接通信求最少广播源数量。这时候就不要建 N×N 矩阵了直接用并查集处理边即可for (int k 0; k m; k) { int u sc.nextInt(); int v sc.nextInt(); union(u - 1, v - 1); // 注意站点编号从1开始还是从0开始 }统计根数量的部分完全一样。用并查集处理边列表时间复杂度可以降到接近 O(N M)而用邻接矩阵会浪费大量空间。5.2 进阶问法最少加几条线让全网互通同一个并查集做完之后如果题目继续问“现在想让所有广播站都处于同一个网络里最少还需要增加几条直接连接”答案就是连通分量数减 1。理由很直观要把 K 个独立连通块变成一个连通块最少的办法就是拿 K-1 条边把它们串成一条链。这算是“发广播”最常见的变体我遇到至少两次一次是在模拟卷里一次是群友面经里看到的。5.3 有向图情况下的不同结论如果题目明确说广播只能沿某个方向转发比如matrix[i][j] 1只表示 i 能向 j 发j 不一定能向 i 发那么问题就不再是数连通分量了。因为一个强连通分量内部可以互动但缩点之后会形成有向无环图要让每个强连通分量都能被至少一个源覆盖并且源之间不能互相到达最少源数等于缩点后入度为 0 的强连通分量个数。这要用 Tarjan 或 Kosaraju 算法。OD机试里这类题相对少见但“发广播”这种名字容易让人往有向图方向想所以看到题目时一定要确认能否回传。5.4 如果N非常大怎么优化假设 N 到了 10000N×N 的矩阵直接开不出来这时要确认题目到底给的是矩阵还是边。如果仍给矩阵但规模很大就要想办法避免全量遍历但一般机试不会这么极端。退一步说真遇到稀疏图建邻接表然后 DFS时间接近 O(NE)。OD机试通常不会考到需要高级剪枝的规模但作为扩展知识知道“稀疏图用邻接表稠密图用矩阵”这个原则就够了。6. 刷题复盘我踩过的坑和一点体会6.1 三次提交的复盘第一次写的时候我把遍历函数写成了“只沿着一条路走到黑”的单分支遍历导致同一个连通分量的点没被完全标记完答案偏大。后来 debug 发现DFS 里的循环一定不能漏掉所有邻居要遍历整行矩阵而不是只沿着第一个找到的1往下走。很多新手都会错在写DFS时不自觉把它当成“链表遍历”以为从当前节点走到下一个节点就完了忘了图的分支结构。第二次是读入时我一开始用charAt方式处理带空格的矩阵结果把空格也当成了节点报数字转换错误。那次之后我就坚持“先看样例再选输入解析方式”宁可多花十秒钟审题也不要写完代码才发现输入格式没对上。第三次是边界测试。N1 时答案应该是 1没有任何连接时答案是 N完全图时答案是 1。把这些边界想清楚提交的时候会安心很多。建议每次写图论题都先用这几个极简用例自测一遍基本能过滤掉八成的低级错误。6.2 考场上的实用建议“发广播”给我的最大收获是不要急着写代码先把“最少几个源”翻译成“几个连通块”。这个建模过程一旦完成后面的代码其实都是套路。反过来如果建模错了代码写再溜也白搭。做题这么多年我发现图论题里一半以上的失误都出在“没看清题目的关系定义”上而不是算法不会。如果你正在准备华为OD机试建议把 DFS 版和并查集版都亲手写一遍再试着自己改成“最少加几条线”的版本。同一个题吃透三个问法比盲目刷十道新题更有效。机试考的不只是算法记忆还有你在限定时间内把题目翻译成代码的能力。这种能力没有捷径只能靠一道一道题积累。
最近集中刷华为OD机试真题做到“发广播”这道题的时候我停顿了一下。题目本身不难但第一次做的时候我直接把它理解成了“从一个站点出发最多能覆盖多少站点”样例轻松通过提交却挂了。重新读题才意识到它真正要的答案是整个广播网络里最少需要选几个站点作为初始广播源才能让所有站点都收到广播。翻译成图论语言就是数无向图的连通分量个数。这篇文章想把我的完整思考过程、两种主流写法DFS/BFS 和并查集以及考试场景下输入输出的处理细节都整理出来。对于正在准备华为OD机试尤其是Java方向、C卷ACM模式的朋友可以直接参考。这道题在OD机试里属于“看着简单但容易栽在建模上”的典型既考邻接矩阵遍历又考对连通性概念的理解。平时如果不注意这一类题考场上很容易在第一步就跑偏。1. 题目理解与核心考点1.1 题目场景到底在问什么先给出一个常见的题目版本大家在各种OD题库里看到的“发广播”基本是这个意思N个广播站组成一个广播网用一个 N×N 的矩阵 connection 表示站点之间的相邻关系connection[i][j] 1 表示站点 i 和站点 j 可以直接通信0 表示不能直接通信主对角线 connection[i][i] 也固定为 1。如果从某个站点发出广播信号会沿着所有能通信的路径自动转发最终能传到所有直接或间接连通的站点。问最少需要从多少个站点主动发起广播才能让全网所有站点都收到至少一次广播读完题别急着写代码。这里有一个关键动作把自然语言翻译成数学模型。“信号会沿着所有能通信的路径自动转发”意味着什么意味着只要两个站点之间存在一条直接或间接的路径它们就属于同一个“可互相到达”的整体。这种关系在离散数学里叫等价关系满足自反、对称、传递。整张网会被划分成若干个互不可达的连通块每个连通块内部任意两点都能互相通信块与块之间没有任何路径。那么我们最少需要从几个站点发起广播答案就是连通块的数量。道理很简单每个连通块内部选一个站点发广播信号就能覆盖整个块不同的连通块之间没有路径你在块A里无论怎么发都进不了块B所以每个块都至少要有一个发起源。反过来每个连通块恰好选一个也一定够。因此“发广播”这道题问的其实是给定一个无向图数一数图里有多少个连通分量。这个转化看起来简单但考场上一紧张就可能跑偏。我当时就是把“从一个点出发能访问到多少个点”和“最少需要几个起点”混在一起答案直接变成了最大可达节点数浪费了不少时间。1.2 为什么是连通分量而不是“可达范围”很多人卡在这道题是因为同时想到了两个概念单点可达集合和全局连通分量。这两种问法结果完全不同。如果题目问的是“从第 k 个站点发广播最多能覆盖多少个站点”那就是单源可达的节点数属于图的遍历题用一次 DFS 或 BFS 从指定起点开始统计访问了几个节点就行。但“发广播”问的是“最少需要几个起点才能覆盖全部”这就是全局规划问题。由于一个起点只能覆盖它所在的连通分量所以全局最少起点数就是连通分量个数。如果误当成前者只跑一次 DFS那当然会漏掉很多未覆盖区域。所以做题第一步永远是划重点题目里有没有“最少需要几个源”“所有点都要覆盖到”这种词。有就大概率是连通分量计数而不是单点可达。这个判断能力比背模板重要得多。1.3 解法选型DFS/BFS还是并查集明确了要数连通分量剩下就是实现路径的选择。邻接矩阵版DFS最直观代码量最少二三十行能搞定。对每个未访问节点执行dfs每次进入一个新的未访问节点就把答案加1适合矩阵规模在几百或一千以内的题目。邻接矩阵版并查集先让每个节点自成一派再扫描矩阵中有连接的位置执行合并最后统计还有多少个根。代码稍长但是逻辑非常统一不太依赖递归。邻接表版BFS如果题目输入给的是边列表而不是矩阵用邻接表配合队列更合适。对于OD机试的“发广播”矩阵规模通常不会特别大一般N≤200或N≤1000两种主流写法都能过。如果让我推荐我首选并查集。原因后面会细说一是省去递归不会因为路径太长导致栈溢出二是后面很多变体题比如“最少加几条线能全网互通”可以直接复用同一个并查集三是它更贴近“合并集合”的语义容易排查错误。2. 解法一DFS/BFS 遍历连通分量2.1 套路与模板DFS解法其实就是“染色法”的图版。维护一个 boolean[] visited长度为 N初始全部为 false。外层循环从 0 到 N-1 一次检查每个站点如果当前站点 i 还没被访问说明它属于一个全新的连通分量此时答案 ans 加 1然后以 i 为起点做一次 DFS凡是能从 i 到达的站点全部标记 visited true继续外层循环直到所有站点都已被访问过。这样外层循环每遇到一个“还没被访问过”的节点就必然发现一个新的连通分量。可以把每个连通分量理解为一种颜色DFS就是给整块区域上色外层循环数一数一共用了多少种颜色。BFS写法只是把递归栈换成显式队列本质没有区别。如果担心递归深度或平台对递归栈不友好就优先用BFS。从上到下的思路几乎一样只是把“递归找邻居”变成了“队列循环弹出”。2.2 Java实现含注释import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[][] grid new int[n][n]; for (int i 0; i n; i) { for (int j 0; j n; j) { grid[i][j] sc.nextInt(); } } boolean[] visited new boolean[n]; int ans 0; for (int i 0; i n; i) { if (!visited[i]) { ans; dfs(grid, visited, i, n); } } System.out.println(ans); } private static void dfs(int[][] grid, boolean[] visited, int i, int n) { visited[i] true; for (int j 0; j n; j) { if (grid[i][j] 1 !visited[j]) { dfs(grid, visited, j, n); } } } }这段代码里有几个细节要说明。第一ji的格子不用特殊处理。因为进入dfs时立刻把visited[i]置为 true循环到ji时会因为!visited[j]不成立而跳过不会造成自循环。第二grid[i][j] 1这个判断实际上把矩阵当成了邻接矩阵来用时间复杂度必然达到 O(N²)。N 在 1000 以内没问题但 N 到 5000 甚至更高时就要考虑用邻接表或优化输入。第三如果矩阵不保证对称比如只有grid[i][j] 1但grid[j][i]可能是0这个DFS仍然把它当成无向图的遍历来跑。因为在“广播能原路返回”的语义下路径是双向的只要 i 能到 j我们就认为 j 能到 i。如果题目明确说是单向转发那就要换解法了这点我在第5章会单独说。2.3 BFS版本如果你想用BFS把dfs调用替换成下面这段即可QueueInteger queue new ArrayDeque(); visited[i] true; queue.offer(i); while (!queue.isEmpty()) { int cur queue.poll(); for (int j 0; j n; j) { if (grid[cur][j] 1 !visited[j]) { visited[j] true; queue.offer(j); } } }注意这里有一个新手容易犯的错在queue.offer(j)之前就已经把visited[j]置为 true而不是等 poll 出来再置。原因是避免同一个节点被多个邻居重复入队。如果等出队才标记那么在一个完全图中第一个节点会把 N-1 个邻居都入队第二个节点出队时会再次判断这些邻居是否已访问虽然逻辑对但队列可能膨胀效率变差。刷OJ时尽量做到“入队即标记”这是一个很通用的BFS优化习惯。3. 解法二并查集Union-Find3.1 并查集在做什么并查集很适合这类“元素之间有关系要划分类别”的问题。一句话解释它维护了一个“谁和谁是同一伙”的集合关系支持两种操作——查find和并union。find(x)找到 x 这个元素所在集合的代表元素一般叫根。为了加快速度过程中会做路径压缩让 x 直接指向根。union(x, y)把 x 和 y 所在的两个集合合并成一个。用在“发广播”上初始时每个站点单独成为一个集合也就是说每个站点的根都是自己。然后遍历连接矩阵发现grid[i][j] 1就把 i 和 j 所在集合合并。所有连接处理完之后再统计有多少个集合的根还是自己这个数量就是连通分量数也就是答案。可以打个比方社团招新。一开始每个人都是只有自己的小社团只要两人有关系就把两边社团合并处理完所有关系后数一数还剩多少个独立社团就是最少需要的广播源数量。3.2 Java实现import java.util.Scanner; public class Main { static int[] parent; static int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩 } return parent[x]; } static void union(int a, int b) { int rootA find(a); int rootB find(b); if (rootA ! rootB) { parent[rootB] rootA; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[][] matrix new int[n][n]; for (int i 0; i n; i) { for (int j 0; j n; j) { matrix[i][j] sc.nextInt(); } } parent new int[n]; for (int i 0; i n; i) { parent[i] i; } // 只看上三角避免同一对连接处理两遍 for (int i 0; i n; i) { for (int j i 1; j n; j) { if (matrix[i][j] 1) { union(i, j); } } } int ans 0; for (int i 0; i n; i) { if (parent[i] i) { ans; } } System.out.println(ans); } }这段代码有一个必须强调的点统计根节点之前最好对每个节点都先执行一次find(i)把整棵树的节点都压缩到根下。上面这段代码其实并不一定需要全量find因为路径压缩是递归做的且我们只关心parent[i] i的数量不可能因为压缩不足而多算或少算。但严谨一点可以在统计前加一个 for 循环for (int i 0; i n; i) { find(i); }这样保证所有 parent 都指向最顶层的根。虽然不压缩也能统计对但压缩之后逻辑更清晰也方便你debug时打印parent数组。3.3 两种解法的对比对比项DFS/BFS并查集代码量更少稍微长一点递归风险DFS有风险BFS无无find递归深度受路径压缩控制时间O(N²)O(N²·α(N))α接近常数空间visited O(N)递归栈O(N)parent O(N)扩展性换题目可能要重写加边、动态合并很方便实际做题选哪个都可以。如果实在拿不准我建议先用DFS快速验证思路再把并查集版本也写一遍这样两种套路都练了考场上换着来也不慌。4. OD机试实战输入输出与AC细节4.1 看清是ACM模式还是核心代码模式华为OD机试有两种常见出题方式。一种是“核心代码”模式平台已经帮你把输入解析好只让你实现一个方法方法入参是矩阵返回值是答案。另一种是ACM模式需要自己写public static void main自己读输入、自己输出。现在不少题目两种模式都可能出甚至有同学反映OD更偏ACM模式所以要两手准备。核心代码模式下的函数大概长这样public int minBroadcastSources(int[][] grid, int n) { // 在这里面写DFS或并查集 return ans; }ACM模式就是要写完整程序上面我给的代码就是ACM模式的写法。准备OD机试建议每天至少用ACM模式练三题否则到了考场上可能会在输入解析上卡住反而不如核心代码模式舒服。4.2 矩阵输入的三种姿势第一种Scanner配合nextInt()。代码简单适合 N 较小的情况。如果 N 到 1000矩阵有 100 万个整数Scanner勉强能跑但在平台超时边缘时容易出问题。第二种BufferedReaderStringTokenizer。BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine().trim()); int[][] matrix new int[n][n]; for (int i 0; i n; i) { StringTokenizer st new StringTokenizer(br.readLine()); for (int j 0; j n; j) { matrix[i][j] Integer.parseInt(st.nextToken()); } }这是我个人在OD机试里最推荐的写法读取速度快逻辑也清晰。很多大矩阵TLE其实不是算法问题而是输入方式太慢。第三种有的题把矩阵每行写成连续字符串比如110\n101\n011这时候不能按数字读取要先按行读进来再用charAt(j) - 0转成整数。for (int i 0; i n; i) { String line br.readLine().trim(); for (int j 0; j n; j) { matrix[i][j] line.charAt(j) - 0; } }如果是这种格式题目描述里一定会有提示比如“矩阵元素之间没有空格”。考试时一定要先看样例输入长什么样再决定用哪种解析方式。这个习惯能省掉很多莫名其妙的运行错误。4.3 统计答案前要不要再find一遍前面说过并查集统计根节点的标准做法是int ans 0; for (int i 0; i n; i) { if (find(i) i) { ans; } }这样写等于在统计的同时完成路径压缩最稳。如果只判断parent[i] i大部分时候结果也对但遇到父节点还没完全压平的情况可能让人产生困惑。用find(i)当条件每次都会返回真正的根可靠性和可读性都更好。另外union的时候可以加一个小优化“按大小合并”把小树并入大树避免形成很深的链。对于 N 这么大的矩阵来说路径压缩已经足够不写按大小合并也能过但写成parent[rootB] rootA这种不平衡合并在极端情况下可能导致find的递归链变长。想更稳就加一个size数组。4.4 题目里的“1”到底代表什么还有一个高频坑题目矩阵里的1到底代表“连接”还是“可达”如果是“连接”那么只有直接相邻的站点能一步到达我们才把它合并如果是“可达”那可能已经包含了间接关系这时你根本不用遍历数数就行因为可达矩阵的连通分量可以直接通过“闭包”来算。OD题库里常见的是连接矩阵也就是邻接矩阵需要我们用图算法去推导间接关系。遇到题目时先看题目定义有没有“直接”“相邻”“一步可达”这类词。4.5 控制复杂度别在遍历时重复合并在并查集写法里如果矩阵是对称的i和j的连接关系会在matrix[i][j]和matrix[j][i]各出现一次。我们只遍历j i 1到 N-1也就是上三角能省掉一半无效合并。如果你是见一个合并一个把整个矩阵都扫了也没问题因为union里rootA ! rootB的判断会过滤掉重复合并但白白多做一些find。N 小无所谓N 大时还是要养成“无向图只看上三角”的习惯。5. 变体与举一反三5.1 输入变成边列表有些题不直接给矩阵而是给 N 和 M 条边。比如输入 N 和 M接下来 M 行每行两个整数 u v表示站点 u 和 v 可以直接通信求最少广播源数量。这时候就不要建 N×N 矩阵了直接用并查集处理边即可for (int k 0; k m; k) { int u sc.nextInt(); int v sc.nextInt(); union(u - 1, v - 1); // 注意站点编号从1开始还是从0开始 }统计根数量的部分完全一样。用并查集处理边列表时间复杂度可以降到接近 O(N M)而用邻接矩阵会浪费大量空间。5.2 进阶问法最少加几条线让全网互通同一个并查集做完之后如果题目继续问“现在想让所有广播站都处于同一个网络里最少还需要增加几条直接连接”答案就是连通分量数减 1。理由很直观要把 K 个独立连通块变成一个连通块最少的办法就是拿 K-1 条边把它们串成一条链。这算是“发广播”最常见的变体我遇到至少两次一次是在模拟卷里一次是群友面经里看到的。5.3 有向图情况下的不同结论如果题目明确说广播只能沿某个方向转发比如matrix[i][j] 1只表示 i 能向 j 发j 不一定能向 i 发那么问题就不再是数连通分量了。因为一个强连通分量内部可以互动但缩点之后会形成有向无环图要让每个强连通分量都能被至少一个源覆盖并且源之间不能互相到达最少源数等于缩点后入度为 0 的强连通分量个数。这要用 Tarjan 或 Kosaraju 算法。OD机试里这类题相对少见但“发广播”这种名字容易让人往有向图方向想所以看到题目时一定要确认能否回传。5.4 如果N非常大怎么优化假设 N 到了 10000N×N 的矩阵直接开不出来这时要确认题目到底给的是矩阵还是边。如果仍给矩阵但规模很大就要想办法避免全量遍历但一般机试不会这么极端。退一步说真遇到稀疏图建邻接表然后 DFS时间接近 O(NE)。OD机试通常不会考到需要高级剪枝的规模但作为扩展知识知道“稀疏图用邻接表稠密图用矩阵”这个原则就够了。6. 刷题复盘我踩过的坑和一点体会6.1 三次提交的复盘第一次写的时候我把遍历函数写成了“只沿着一条路走到黑”的单分支遍历导致同一个连通分量的点没被完全标记完答案偏大。后来 debug 发现DFS 里的循环一定不能漏掉所有邻居要遍历整行矩阵而不是只沿着第一个找到的1往下走。很多新手都会错在写DFS时不自觉把它当成“链表遍历”以为从当前节点走到下一个节点就完了忘了图的分支结构。第二次是读入时我一开始用charAt方式处理带空格的矩阵结果把空格也当成了节点报数字转换错误。那次之后我就坚持“先看样例再选输入解析方式”宁可多花十秒钟审题也不要写完代码才发现输入格式没对上。第三次是边界测试。N1 时答案应该是 1没有任何连接时答案是 N完全图时答案是 1。把这些边界想清楚提交的时候会安心很多。建议每次写图论题都先用这几个极简用例自测一遍基本能过滤掉八成的低级错误。6.2 考场上的实用建议“发广播”给我的最大收获是不要急着写代码先把“最少几个源”翻译成“几个连通块”。这个建模过程一旦完成后面的代码其实都是套路。反过来如果建模错了代码写再溜也白搭。做题这么多年我发现图论题里一半以上的失误都出在“没看清题目的关系定义”上而不是算法不会。如果你正在准备华为OD机试建议把 DFS 版和并查集版都亲手写一遍再试着自己改成“最少加几条线”的版本。同一个题吃透三个问法比盲目刷十道新题更有效。机试考的不只是算法记忆还有你在限定时间内把题目翻译成代码的能力。这种能力没有捷径只能靠一道一道题积累。
