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

文章目录

相关推荐阅读

题目练习网址：【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或了解更多

# 算法 # 深度优先 # 宽度优先 # java # c++ # python
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

WRB1205S-1WR2 与钡特电源 VB1-12S05S 参数规格解析｜ 1W 宽压输入隔离 DC-DC 工业电源模块性能拆解

avatar 亚马逊云科技技术品牌专区
cover

人工智能如何改变学习方式

avatar 亚马逊云科技技术品牌专区
cover

FPGA 人工智能开发新手入门指南

avatar 亚马逊云科技技术品牌专区