2026华为OD机试真题 10月18日 新系统 【小花的AI Workflow设计】

小花的AI Workflow设计(Py/C/C++/JAVA /Js/Go)题解

华为OD机试真题 新系统 华为OD上机考试真题新系统 10月18号 100分题型

华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录｜机考题库 + 算法考点详解

题目内容

小花正在设计一个基于大模型的 AI Workflow 系统。Workflow 由多个 AI 处理节点组成，节点编号从

1

1

1 到

n

n

n。 某些节点必须在其他节点完成后才能执行，形成了节点之间的依赖关系。这种依赖关系构成了一个有向无环图（DAG）。 给定节点数量

n

n

n、依赖关系列表 edges、起始节点

s

s

s 和终止节点

t

t

t，求从起始节点

s

s

s 到终止节点

t

t

t 的所有可能执行路径数量。 输入参数：

• n：整数，节点数量，$1\le n\le 10000$
• edges：二维整数数组，表示依赖关系。edges[i] = [u, v] 表示节点 $u$
• s：整数，起始节点编号，$1\le s\le n$
• t：整数，终止节点编号，$1\le t\le n$

约束条件：

返回值：返回从

s

s

s 到

t

t

t 的路径总数。

特殊场景：

输入描述

输入格式如下

n
u,v u,v u,v …
s t

• n :整数，节点数量

• 边列表内部，每个端点对写作 u,v，端点对之间用 空格 分隔；没有依赖关系时为空字符串。

• s:整数，起始节点编号

• t:整数，终点节点编号

数据范围：

• $1\le n\le 10000$
• $0\le \text{edges.length}\le 100000$
• 每条依赖 $[u,v]$
• 依赖关系保证无环；
• $1\le s,t\le n$

输出描述

输出一行一个十进制整数，表示从

s

s

s 到

t

t

t 的路径总数。

• 若 $s=t$
• 若从 $s$
• 数据保证答案不超过 $2^{31}-1$

样例1

输入

4
1,2 1,3 2,4 3,4
1 4

输出

2

说明

1
/ \\
2 3
\\ /
4

从节点 1 到节点 4 有两条路径：

1

→

2

→

4

1 \\to 2 \\to 4

1→2→4 和

1

→

3

→

4

1 \\to 3 \\to 4

1→3→4。

样例2

输入

6
1,2 1,3 2,4 3,5 4,5 5,6
1 6

输出

2

说明

1
/ \\
2 3
| |
4 |
\\ /
5
|
6

从节点 1 到节点 6 有两条路径：

1

→

2

→

4

→

5

→

6

1 \\to 2 \\to 4 \\to 5 \\to 6

1→2→4→5→6 和

1

→

3

→

5

→

6

1 \\to 3 \\to 5 \\to 6

1→3→5→6。

样例3

输入

4
1,2 3,4
1 4

输出

0

说明 节点

{

1

,

2

}

\\{1, 2\\}

{1,2} 与

{

3

,

4

}

\\{3, 4\\}

{3,4} 属于两个不连通的子图，从节点 1 无法到达节点 4，路径数为 0。

样例4

输入

1

1 1

输出

1

说明 只有一个节点，起始节点和终止节点相同，无需执行其他节点，路径数为 1。

题解

思路：动态规划 + 拓扑排序

C++

#include <bits/stdc++.h>
#include <queue>
#include <vector>
using namespace std;

// 通用 切割函数 函数 将字符串str根据delimiter进行切割
vector<string> split(const string& str, const string& delimiter) {
vector<string> result;
size_t start = 0;
size_t end = str.find(delimiter);
while (end != string::npos) {
result.push_back(str.substr(start, end – start));
start = end + delimiter.length();
end = str.find(delimiter, start);
}
// 添加最后一个部分
result.push_back(str.substr(start));
return result;
}

int solve(int n, vector<vector<int>>& edge, int s, int t) {
if (s == t) {
return 1;
}
// 邻接表
vector<vector<int>> graph(n + 1);
// 统计入度
vector<int> indegree(n + 1, 0);
// 表示从起点 s 到节点 i 的路径数量
vector<int> dp(n + 1, 0);
for (auto& e : edge) {
int u = e[0], v = e[1];
graph[u].push_back(v);
indegree[v]++;
}
dp[s] = 1;
queue<int> q;
for (int i = 0; i <= n; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
//拓扑排序求路径
while(!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
dp[v] += dp[u];
indegree[v]—;
if (indegree[v] == 0) {
q.push(v);
}
}
}
return dp[t];
}

int main() {
int n;
string input1;
int s,t;
cin >> n;
cin.ignore();
getline(cin, input1);
cin >> s >> t;
vector<vector<int>> edge;
if (!input1.empty()) {
vector<string> tmp = split(input1, " ");
for (int i = 0; i < tmp.size(); i++) {
vector<string> tmp1 = split(tmp[i], ",");
edge.push_back({stoi(tmp1[0]),stoi(tmp1[1])});
}
}
int ans = solve(n, edge, s, t);
cout << ans;
return 0;
}

Java

import java.util.*;

public class Main {

public static int solve(int n, int[][] edge, int s, int t) {
if (s == t) {
return 1;
}

// 邻接表
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}

// 统计入度
int[] indegree = new int[n + 1];

// 表示从起点 s 到节点 i 的路径数量
int[] dp = new int[n + 1];

for (int[] e : edge) {
int u = e[0], v = e[1];
graph.get(u).add(v);
indegree[v]++;
}

dp[s] = 1;

Queue<Integer> q = new LinkedList<>();
for (int i = 0; i <= n; i++) {
if (indegree[i] == 0) {
q.offer(i);
}
}

// 拓扑排序求路径
while (!q.isEmpty()) {
int u = q.poll();

for (int v : graph.get(u)) {
dp[v] += dp[u];
indegree[v]—;

if (indegree[v] == 0) {
q.offer(v);
}
}
}

return dp[t];
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
sc.nextLine();

String input1 = sc.nextLine();

int s = sc.nextInt();
int t = sc.nextInt();

List<int[]> edges = new ArrayList<>();

if (!input1.trim().isEmpty()) {
String[] tmp = input1.trim().split("\\\\s+");

for (String str : tmp) {
String[] tmp1 = str.split(",");
edges.add(new int[]{
Integer.parseInt(tmp1[0]),
Integer.parseInt(tmp1[1])
});
}
}

int[][] edge = edges.toArray(new int[0][]);

int ans = solve(n, edge, s, t);
System.out.println(ans);

sc.close();
}
}

Python

from collections import deque

def solve(n, edge, s, t):
if s == t:
return 1

# 邻接表
graph = [[] for _ in range(n + 1)]

# 统计入度
indegree = [0] * (n + 1)

# 表示从起点 s 到节点 i 的路径数量
dp = [0] * (n + 1)

for u, v in edge:
graph[u].append(v)
indegree[v] += 1

dp[s] = 1

q = deque()
for i in range(n + 1):
if indegree[i] == 0:
q.append(i)

# 拓扑排序求路径
while q:
u = q.popleft()

for v in graph[u]:
dp[v] += dp[u]
indegree[v] -= 1

if indegree[v] == 0:
q.append(v)

return dp[t]

def main():
n = int(input())
input1 = input().strip()

s, t = map(int, input().split())

edge = []

if input1:
tmp = input1.split()

for item in tmp:
u, v = map(int, item.split(','))
edge.append([u, v])

ans = solve(n, edge, s, t)
print(ans)

if __name__ == "__main__":
main()

JavaScript

const readline = require('readline');

const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});

let lines = [];

rl.on('line', line => {
lines.push(line);

if (lines.length === 3) {
const n = parseInt(lines[0]);
const input1 = lines[1].trim();

const [s, t] = lines[2].trim().split(/\\s+/).map(Number);

const edge = [];

if (input1) {
const tmp = input1.split(/\\s+/);

for (const item of tmp) {
const [u, v] = item.split(',').map(Number);
edge.push([u, v]);
}
}

const ans = solve(n, edge, s, t);
console.log(ans);

rl.close();
}
});

function solve(n, edge, s, t) {
if (s === t) {
return 1;
}

// 邻接表
const graph = Array.from({ length: n + 1 }, () => []);

// 统计入度
const indegree = new Array(n + 1).fill(0);

// 表示从起点 s 到节点 i 的路径数量
const dp = new Array(n + 1).fill(0);

for (const [u, v] of edge) {
graph[u].push(v);
indegree[v]++;
}

dp[s] = 1;

const q = [];
let head = 0;

for (let i = 0; i <= n; i++) {
if (indegree[i] === 0) {
q.push(i);
}
}

// 拓扑排序求路径
while (head < q.length) {
const u = q[head++];

for (const v of graph[u]) {
dp[v] += dp[u];
indegree[v]—;

if (indegree[v] === 0) {
q.push(v);
}
}
}

return dp[t];
}

Go

package main

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

func solve(n int, edge [][]int, s int, t int) int {
if s == t {
return 1
}

// 邻接表
graph := make([][]int, n+1)

// 统计入度
indegree := make([]int, n+1)

// 表示从起点 s 到节点 i 的路径数量
dp := make([]int, n+1)

for _, e := range edge {
u, v := e[0], e[1]
graph[u] = append(graph[u], v)
indegree[v]++
}

dp[s] = 1

q := make([]int, 0)
for i := 0; i <= n; i++ {
if indegree[i] == 0 {
q = append(q, i)
}
}

// 拓扑排序求路径
head := 0
for head < len(q) {
u := q[head]
head++

for _, v := range graph[u] {
dp[v] += dp[u]
indegree[v]—

if indegree[v] == 0 {
q = append(q, v)
}
}
}

return dp[t]
}

func main() {
reader := bufio.NewReader(os.Stdin)

line1, _ := reader.ReadString('\\n')
n, _ := strconv.Atoi(strings.TrimSpace(line1))

input1, _ := reader.ReadString('\\n')
input1 = strings.TrimSpace(input1)

line3, _ := reader.ReadString('\\n')
st := strings.Fields(line3)

s, _ := strconv.Atoi(st[0])
t, _ := strconv.Atoi(st[1])

edge := make([][]int, 0)

if input1 != "" {
tmp := strings.Fields(input1)

for _, item := range tmp {
tmp1 := strings.Split(item, ",")

u, _ := strconv.Atoi(tmp1[0])
v, _ := strconv.Atoi(tmp1[1])

edge = append(edge, []int{u, v})
}
}

ans := solve(n, edge, s, t)
fmt.Println(ans)
}

C语言

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

#define MAXN 100005
#define MAXE 200005

int head[MAXN];
int to[MAXE];
int next[MAXE];
int indegree[MAXN];
int dp[MAXN];
int edgeCount = 0;

// 添加有向边
void addEdge(int u, int v) {
to[edgeCount] = v;
next[edgeCount] = head[u];
head[u] = edgeCount++;
}

int solve(int n, int edge[][2], int m, int s, int t) {
if (s == t) {
return 1;
}

// 邻接表初始化
for (int i = 0; i <= n; i++) {
head[i] = –1;
indegree[i] = 0;
dp[i] = 0;
}

edgeCount = 0;

// 构建邻接表并统计入度
for (int i = 0; i < m; i++) {
int u = edge[i][0];
int v = edge[i][1];

addEdge(u, v);
indegree[v]++;
}

// 表示从起点 s 到节点 i 的路径数量
dp[s] = 1;

int *q = (int *)malloc((n + 1) * sizeof(int));
int front = 0, rear = 0;

for (int i = 0; i <= n; i++) {
if (indegree[i] == 0) {
q[rear++] = i;
}
}

// 拓扑排序求路径
while (front < rear) {
int u = q[front++];

for (int i = head[u]; i != –1; i = next[i]) {
int v = to[i];

dp[v] += dp[u];
indegree[v]—;

if (indegree[v] == 0) {
q[rear++] = v;
}
}
}

int ans = dp[t];
free(q);

return ans;
}

int main() {
int n, s, t;
char input1[1000000];

scanf("%d", &n);
getchar();

fgets(input1, sizeof(input1), stdin);

scanf("%d %d", &s, &t);

int edge[MAXE][2];
int m = 0;

// 解析边
char *token = strtok(input1, " \\n\\r");

while (token != NULL) {
int u, v;

if (sscanf(token, "%d,%d", &u, &v) == 2) {
edge[m][0] = u;
edge[m][1] = v;
m++;
}

token = strtok(NULL, " \\n\\r");
}

int ans = solve(n, edge, m, s, t);
printf("%d", ans);

return 0;
}