20天拿下华为OD笔试之【DFS/BFS】2025C-广播服务器【Py/Java/C++/C/JS/Go六种语言OD独家2025C卷真题】【欧弟算法】全网注释最详细分类最全的华子OD真题题解

可上 欧弟OJ系统 练习华子OD、大厂真题 绿色聊天软件戳 od1441了解算法冲刺训练（备注【CSDN】否则不通过）

文章目录

• 相关推荐阅读
• 题目描述与示例
• • 题目描述
  • 输入
  • 输出
  • 示例一
  • • 输入
    • 输出
  • 示例二
  • • 输入
    • 输出
• 解题思路
• 代码
• • 解法一：BFS
  • • Python
    • Java
    • C++
    • C
    • Node JavaScript
    • Go
  • 解法二：DFS
  • • Python
    • Java
    • C++
    • C
    • Node JavaScript
    • Go
  • 时空复杂度
• 相同问题不同描述
• • 2023B-快递业务站
  • • 题目
    • 输入描述
    • 输出描述
    • 示例一
    • • 输入
      • 输出
      • 说明
    • 示例二
    • • 输入
      • 输出
      • 说明
• 华为OD算法/大厂面试高频题算法练习冲刺训练

相关推荐阅读

• 【华为OD机考】2025C+2025B+2024E+D卷真题【完全原创题解 | 详细考点分类 | 不断更新题目】
• 【华为OD笔试】2025C+2025B+2024E+D卷真题机考套题汇总【真实反馈，不断更新，限时免费】
• 【华为OD笔试】2024E+D卷命题规律解读【分析500+场OD笔试考点总结】
• 【华为OD流程】性格测试选项+注意事项】

题目练习网址：【DFS/BFS】2025C-广播服务器

题目描述与示例

题目描述

服务器连接方式包括直接相连，间接连接。A 和 B 直接连接，B 和 C 直接连接，则 A 和 C 间接连接。 直接连接和间接连接都可以发送广播。 给出一个大小为 N*N 的二维矩阵matrix，代表 N 个服务器。matrix[i][j] = 1，则代表 i 和 j 直接连接；matrix[i][j] = 0 时，代表 i 和 j 不直接连接。matrix[i][j]==1，即自己和自已直接连接。 计算初始需要给几台服务器广播，才可以使每个服务器都收到广播。

输入

输入为 N 行，每行有 N 个数字，为 0 成 1，由空格分隔，构成 N*N 的二维矩阵matrix，N 的范围为 1 <= N <= 40。

输出

输出一个数字，为需要广播的服务器的数量。

示例一

输入

1 0 0
0 1 0
0 0 1

输出

3

示例二

输入

1 1
1 1

输出

1

解题思路

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

代码

解法一：BFS

Python

# 欢迎来到「欧弟算法 – 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 题目：2025A/2024E/2025C-广播服务器
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问

from collections import deque

isConnected = list()
# 先输入第一行
isConnected.append(list(map(int, input().split())))
# 根据第一行的长度，得到n
n = len(isConnected[0])
# 输入剩余的n-1行
for _ in range(n–1):
isConnected.append(list(map(int, input().split())))

ans = 0
checkList = [0] * n # 构建检查数组checkList

# 遍历每一个服务器
for i in range(n):
if checkList[i] == 0: # 若服务器i未检查过
q = deque([i]) # 把服务器i加入q中，作为BFS的起始位置
checkList[i] = 1 # 将服务器i标记为已检查过
# 从服务器i开始，进行BFS
while(q):
# 弹出q队头的服务器x，考虑所有与其相连的服务器y
x = q.popleft()
# 对于服务器x，遍历所有其他服务器y，若y未检查过，且与x相连
for y in range(n):
if x != y and checkList[y] == 0 and isConnected[x][y] == 1:
q.append(y) # 则把服务器y加入队列中
checkList[y] = 1 # 同时把服务器y标记为已检查过
# 完成本次BFS，连通分量+1，即ans+1
ans += 1

print(ans)

Java

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
List<List<Integer>> isConnected = new ArrayList<>();

String[] firstLine = scanner.nextLine().split(" ");
List<Integer> firstRow = new ArrayList<>();
for (String s : firstLine) {
firstRow.add(Integer.parseInt(s));
}
isConnected.add(firstRow);

int n = firstRow.size();
for (int i = 1; i < n; i++) {
String[] line = scanner.nextLine().split(" ");
List<Integer> row = new ArrayList<>();
for (String s : line) {
row.add(Integer.parseInt(s));
}
isConnected.add(row);
}

int ans = 0;
int[] checkList = new int[n];

for (int i = 0; i < n; i++) {
if (checkList[i] == 0) {
Queue<Integer> q = new LinkedList<>();
q.add(i);
checkList[i] = 1;

while (!q.isEmpty()) {
int x = q.poll();
for (int y = 0; y < n; y++) {
if (x != y && checkList[y] == 0 && isConnected.get(x).get(y) == 1) {
q.add(y);
checkList[y] = 1;
}
}
}
ans++;
}
}

System.out.println(ans);
}
}

C++

#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
using namespace std;

int main() {
vector<vector<int>> isConnected;
string line;
getline(cin, line);
istringstream iss(line);
int val;
vector<int> firstRow;
while (iss >> val) {
firstRow.push_back(val);
}
isConnected.push_back(firstRow);

int n = firstRow.size();
for (int i = 1; i < n; i++) {
getline(cin, line);
istringstream iss(line);
vector<int> row;
while (iss >> val) {
row.push_back(val);
}
isConnected.push_back(row);
}

int ans = 0;
vector<int> checkList(n, 0);

for (int i = 0; i < n; i++) {
if (checkList[i] == 0) {
queue<int> q;
q.push(i);
checkList[i] = 1;

while (!q.empty()) {
int x = q.front();
q.pop();
for (int y = 0; y < n; y++) {
if (x != y && checkList[y] == 0 && isConnected[x][y] == 1) {
q.push(y);
checkList[y] = 1;
}
}
}
ans++;
}
}

cout << ans << endl;
return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static char* xstrdup(const char* s) {
if (!s) return NULL;
size_t len = strlen(s);
char* p = (char*)malloc(len + 1);
if (!p) {
fprintf(stderr, "malloc failed in xstrdup\\n");
exit(1);
}
memcpy(p, s, len + 1);
return p;
}

/* 读取一整行并去掉结尾换行，成功返回 1，失败返回 0 */
static int read_line(char *buf, int cap) {
if (!fgets(buf, cap, stdin)) return 0;
size_t L = strlen(buf);
while (L && (buf[L–1] == '\\n' || buf[L–1] == '\\r')) buf[—L] = '\\0';
return 1;
}

/* 统计一行中以空白分隔的整数个数（不修改原串；内部复制一份解析） */
static int count_ints_in_line(const char *line) {
char *dup = xstrdup(line);
int cnt = 0;
char *tok = strtok(dup, " \\t");
while (tok) {
cnt++;
tok = strtok(NULL, " \\t");
}
free(dup);
return cnt;
}

/* 解析一行到数组 row[0..n-1]，要求正好解析出 n 个整数 */
static void parse_line_to_row(const char *line, int *row, int n) {
char *dup = xstrdup(line);
int i = 0;
char *tok = strtok(dup, " \\t");
while (tok && i < n) {
row[i++] = (int)strtol(tok, NULL, 10);
tok = strtok(NULL, " \\t");
}
/* 若不足 n 个，剩余位置补 0；若超过则截断 */
while (i < n) row[i++] = 0;
free(dup);
}

int main(void) {
/* 读取第一行，推断矩阵的维度 n */
char line[1 << 16];
if (!read_line(line, sizeof(line))) {
/* 无输入：按 0 输出 */
printf("0\\n");
return 0;
}

int n = count_ints_in_line(line);
if (n <= 0) {
printf("0\\n");
return 0;
}

/* 分配邻接矩阵 isConnected[n][n]，以及 visited 数组 */
int **isConnected = (int **)malloc(n * sizeof(int *));
if (!isConnected) { fprintf(stderr, "malloc fail\\n"); return 1; }
for (int i = 0; i < n; ++i) {
isConnected[i] = (int *)malloc(n * sizeof(int));
if (!isConnected[i]) { fprintf(stderr, "malloc fail\\n"); return 1; }
}

int *visited = (int *)calloc(n, sizeof(int));
if (!visited) { fprintf(stderr, "calloc fail\\n"); return 1; }

/* 解析第一行到矩阵第 0 行 */
parse_line_to_row(line, isConnected[0], n);

/* 继续读取后续 n-1 行，填充矩阵 */
for (int i = 1; i < n; ++i) {
if (!read_line(line, sizeof(line))) {
/* 若行数不足，缺失的行按 0 填充 */
for (int j = 0; j < n; ++j) isConnected[i][j] = 0;
} else {
parse_line_to_row(line, isConnected[i], n);
}
}

/* BFS 统计连通分量个数 */
int ans = 0;
int *queue = (int *)malloc(n * sizeof(int)); /* 简单队列，容量 n 即可 */
if (!queue) { fprintf(stderr, "malloc fail\\n"); return 1; }

for (int i = 0; i < n; ++i) {
if (visited[i] == 0) {
ans++;
int head = 0, tail = 0;
queue[tail++] = i;
visited[i] = 1;

while (head < tail) {
int x = queue[head++];

for (int y = 0; y < n; ++y) {
if (x != y && visited[y] == 0 && isConnected[x][y] == 1) {
visited[y] = 1;
queue[tail++] = y;
}
}
}
}
}

printf("%d\\n", ans);

/* 释放内存 */
free(queue);
for (int i = 0; i < n; ++i) free(isConnected[i]);
free(isConnected);
free(visited);

return 0;
}

Node JavaScript

const fs = require("fs");
const input = fs.readFileSync(0, "utf8").trim().split("\\n");

const n = input[0].trim().split(/\\s+/).length; // 矩阵大小 n

// 构建邻接矩阵
const isConnected = Array.from({ length: n }, (_, i) =>
input[i].trim().split(/\\s+/).map(Number)
);

const visited = Array(n).fill(0);
let ans = 0;

// 遍历所有节点
for (let i = 0; i < n; i++) {
if (visited[i] === 0) {
ans++;
const q = [i];
visited[i] = 1;

while (q.length > 0) {
const x = q.shift();
for (let y = 0; y < n; y++) {
if (x !== y && visited[y] === 0 && isConnected[x][y] === 1) {
visited[y] = 1;
q.push(y);
}
}
}
}
}

console.log(ans.toString());

Go

package main

import (
"bufio"
"fmt"
"os"
"strings"
)

func main() {
in := bufio.NewReader(os.Stdin)
lines := []string{}

// 逐行读取输入
for {
line, err := in.ReadString('\\n')
if err != nil && len(line) == 0 {
break
}
line = strings.TrimSpace(line)
if line != "" {
lines = append(lines, line)
}
}

if len(lines) == 0 {
fmt.Println(0)
return
}

// 矩阵大小 n
firstLine := strings.Fields(lines[0])
n := len(firstLine)

// 构建邻接矩阵
isConnected := make([][]int, n)
for i := 0; i < n; i++ {
isConnected[i] = make([]int, n)
fields := strings.Fields(lines[i])
for j := 0; j < n; j++ {
fmt.Sscanf(fields[j], "%d", &isConnected[i][j])
}
}

visited := make([]int, n)
ans := 0

for i := 0; i < n; i++ {
if visited[i] == 0 {
ans++
queue := []int{i}
visited[i] = 1

for len(queue) > 0 {
x := queue[0]
queue = queue[1:]
for y := 0; y < n; y++ {
if x != y && visited[y] == 0 && isConnected[x][y] == 1 {
visited[y] = 1
queue = append(queue, y)
}
}
}
}
}

fmt.Println(ans)
}

解法二：DFS

Python

# 欢迎来到「欧弟算法 – 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 题目：2025A/2024E/2025C-广播服务器
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问

# dfs递归函数
def dfs(x, isConnected, checkList):
# 对于传入的服务器x，将其标记为已检查过
checkList[x] = 1
# 遍历其他服务器y，若服务器y未检查过，且与服务器x相连
for y in range(n):
if y != x and checkList[y] == 0 and isConnected[x][y] == 1:
dfs(y, isConnected, checkList) # 则对y进行DFS

isConnected = list()
# 先输入第一行
isConnected.append(list(map(int, input().split())))
# 根据第一行的长度，得到n
n = len(isConnected[0])
# 输入剩余的n-1行
for _ in range(n–1):
isConnected.append(list(map(int, input().split())))

ans = 0
checkList = [0] * n # 构建检查数组checkList

# 遍历每一个服务器i
for i in range(n):
# 如果该服务器没检查过，则以服务器i作为起始点，进行DFS
if checkList[i] == 0:
# 进行DFS搜索
dfs(i, isConnected, checkList)
# 完成本次DFS，连通分量+1，即ans+1
ans += 1

print(ans)

Java

import java.util.*;

public class Main {
static void dfs(int x, List<List<Integer>> isConnected, int[] checkList) {
checkList[x] = 1;
int n = isConnected.size();
for (int y = 0; y < n; y++) {
if (y != x && checkList[y] == 0 && isConnected.get(x).get(y) == 1) {
dfs(y, isConnected, checkList);
}
}
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
List<List<Integer>> isConnected = new ArrayList<>();
String[] firstLine = scanner.nextLine().split(" ");
List<Integer> firstRow = new ArrayList<>();
for (String s : firstLine) {
firstRow.add(Integer.parseInt(s));
}
isConnected.add(firstRow);

int n = firstRow.size();
for (int i = 1; i < n; i++) {
String[] line = scanner.nextLine().split(" ");
List<Integer> row = new ArrayList<>();
for (String s : line) {
row.add(Integer.parseInt(s));
}
isConnected.add(row);
}

int ans = 0;
int[] checkList = new int[n];

for (int i = 0; i < n; i++) {
if (checkList[i] == 0) {
dfs(i, isConnected, checkList);
ans++;
}
}

System.out.println(ans);
}
}

C++

#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

void dfs(int x, vector<vector<int>>& isConnected, vector<int>& checkList) {
checkList[x] = 1;
int n = isConnected.size();
for (int y = 0; y < n; y++) {
if (y != x && checkList[y] == 0 && isConnected[x][y] == 1) {
dfs(y, isConnected, checkList);
}
}
}

int main() {
vector<vector<int>> isConnected;
string line;
getline(cin, line);
istringstream iss(line);
int val;
vector<int> firstRow;
while (iss >> val) {
firstRow.push_back(val);
}
isConnected.push_back(firstRow);

int n = firstRow.size();
for (int i = 1; i < n; i++) {
getline(cin, line);
istringstream iss(line);
vector<int> row;
while (iss >> val) {
row.push_back(val);
}
isConnected.push_back(row);
}

int ans = 0;
vector<int> checkList(n, 0);

for (int i = 0; i < n; i++) {
if (checkList[i] == 0) {
dfs(i, isConnected, checkList);
ans++;
}
}

cout << ans << endl;
return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static char* xstrdup(const char* s) {
if (!s) return NULL;
size_t len = strlen(s);
char* p = (char*)malloc(len + 1);
if (!p) exit(1);
memcpy(p, s, len + 1);
return p;
}

/* 读取一整行并去掉结尾换行，成功返回 1，失败返回 0 */
static int read_line(char *buf, int cap) {
if (!fgets(buf, cap, stdin)) return 0;
size_t L = strlen(buf);
while (L && (buf[L–1] == '\\n' || buf[L–1] == '\\r')) buf[—L] = '\\0';
return 1;
}

/* 统计一行中以空白分隔的整数个数 */
static int count_ints_in_line(const char *line) {
char *dup = xstrdup(line);
int cnt = 0;
char *tok = strtok(dup, " \\t");
while (tok) { cnt++; tok = strtok(NULL, " \\t"); }
free(dup);
return cnt;
}

/* 解析一行到数组 row[0..n-1]，不足补 0，超出截断 */
static void parse_line_to_row(const char *line, int *row, int n) {
char *dup = xstrdup(line);
int i = 0;
char *tok = strtok(dup, " \\t");
while (tok && i < n) {
row[i++] = (int)strtol(tok, NULL, 10);
tok = strtok(NULL, " \\t");
}
while (i < n) row[i++] = 0;
free(dup);
}

/* 非递归 DFS：用显式栈，避免递归栈溢出 */
static void dfs_iter(int start, int **isConnected, int n, int *visited) {
int *stack = (int*)malloc(n * sizeof(int));
int top = 0;
stack[top++] = start;
visited[start] = 1;

while (top) {
int x = stack[—top];
/* 扫描与 x 相连的所有点 */
for (int y = 0; y < n; ++y) {
if (y != x && !visited[y] && isConnected[x][y] == 1) {
visited[y] = 1;
stack[top++] = y;
}
}
}
free(stack);
}

int main(void) {
/* 读取第一行，推断矩阵维度 n */
char line[1 << 16];
if (!read_line(line, sizeof(line))) { printf("0\\n"); return 0; }
int n = count_ints_in_line(line);
if (n <= 0) { printf("0\\n"); return 0; }

/* 分配邻接矩阵 isConnected[n][n] 与 visited */
int **isConnected = (int**)malloc(n * sizeof(int*));
if (!isConnected) return 1;
for (int i = 0; i < n; ++i) {
isConnected[i] = (int*)malloc(n * sizeof(int));
if (!isConnected[i]) return 1;
}
int *visited = (int*)calloc(n, sizeof(int));
if (!visited) return 1;

/* 解析第一行到第 0 行 */
parse_line_to_row(line, isConnected[0], n);
/* 解析后续 n-1 行 */
for (int i = 1; i < n; ++i) {
if (!read_line(line, sizeof(line))) {
for (int j = 0; j < n; ++j) isConnected[i][j] = 0;
} else {
parse_line_to_row(line, isConnected[i], n);
}
}

/* 统计连通分量个数（省份数量） */
int ans = 0;
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
dfs_iter(i, isConnected, n, visited);
ans++;
}
}

printf("%d\\n", ans);

/* 释放内存 */
for (int i = 0; i < n; ++i) free(isConnected[i]);
free(isConnected);
free(visited);
return 0;
}

Node JavaScript

const fs = require("fs");
const input = fs.readFileSync(0, "utf8").trim().split("\\n");

// 矩阵大小 n
const n = input[0].trim().split(/\\s+/).length;

// 构建邻接矩阵
const isConnected = Array.from({ length: n }, (_, i) =>
input[i].trim().split(/\\s+/).map(Number)
);

const visited = Array(n).fill(0);

function dfs(x) {
visited[x] = 1;
for (let y = 0; y < n; y++) {
if (y !== x && visited[y] === 0 && isConnected[x][y] === 1) {
dfs(y);
}
}
}

let ans = 0;
for (let i = 0; i < n; i++) {
if (visited[i] === 0) {
dfs(i);
ans++;
}
}

console.log(ans.toString());

Go

package main

import (
"bufio"
"fmt"
"os"
"strings"
)

var (
n int
isConnected [][]int
visited []int
)

func dfs(x int) {
visited[x] = 1
for y := 0; y < n; y++ {
if y != x && visited[y] == 0 && isConnected[x][y] == 1 {
dfs(y)
}
}
}

func main() {
in := bufio.NewReader(os.Stdin)
lines := []string{}

// 逐行读取输入
for {
line, err := in.ReadString('\\n')
if err != nil && len(line) == 0 {
break
}
line = strings.TrimSpace(line)
if line != "" {
lines = append(lines, line)
}
}

if len(lines) == 0 {
fmt.Println(0)
return
}

firstLine := strings.Fields(lines[0])
n = len(firstLine)

// 构建邻接矩阵
isConnected = make([][]int, n)
for i := 0; i < n; i++ {
isConnected[i] = make([]int, n)
fields := strings.Fields(lines[i])
for j := 0; j < n; j++ {
fmt.Sscanf(fields[j], "%d", &isConnected[i][j])
}
}

visited = make([]int, n)
ans := 0
for i := 0; i < n; i++ {
if visited[i] == 0 {
dfs(i)
ans++
}
}

fmt.Println(ans)
}

时空复杂度

时间复杂度：O(N^2)。需要遍历整个关联矩阵 isConnected。

空间复杂度：O(N)。

相同问题不同描述

2023B-快递业务站

题目

快递业务范围有 N 个站点，A 站点与 B 站点可以中转快递，则认为 A-B 站可达。

如果 A-B 可达，B-C 可达，则 A-C 可达。

现在给 N 个站点编号 0, 1, …, n-1，用 s[i][j]表示 i-j 是否可达。

s[i][j] = 1表示 i-j可达，s[i][j] = 0表示 i-j 不可达。

现用二维数组给定N个站点的可达关系，请计算至少选择从几个主站点出发，才能可达所有站点（覆盖所有站点业务）。说明：s[i][j]与s[j][i]取值相同。

输入描述

第一行输入为 N，N表示站点个数。 1 < N < 10000

之后 N 行表示站点之间的可达关系，第i行第j个数值表示编号为i和j之间是否可达。

输出描述

输出站点个数，表示至少需要多少个主站点。

示例一

输入

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

输出

1

说明

选择 0 号站点作为主站点， 0 站点可达其他所有站点， 所以至少选择 1 个站点作为主站才能覆盖所有站点业务

示例二

输入

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

输出

3

说明

选择 0 号站点可以覆盖 0、1 站点， 选择 2 号站点可以覆盖 2 号站点， 选择 3 号站点可以覆盖 3 号站点， 所以至少选择 3 个站点作为主站才能覆盖所有站点业务

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务1000+同学成功上岸！

• 课程讲师为全网200w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 90+天陪伴式学习，100+直播课时，300+动画图解视频，500+LeetCode经典题，500+华为OD真题/大厂真题，还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接OD真题汇总(持续更新)

• 绿色聊天软件戳 od1441或了解更多