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$ 到 $n$。
某些节点必须在其他节点完成后才能执行，形成了节点之间的依赖关系。这种依赖关系构成了一个有向无环图（DAG）。
给定节点数量 $n$、依赖关系列表 edges、起始节点 $s$ 和终止节点 $t$，求从起始节点 $s$ 到终止节点 $t$ 的所有可能执行路径数量。
输入参数：

• n：整数，节点数量，$1\le n\le 10000$。
• edges：二维整数数组，表示依赖关系。edges[i] = [u, v] 表示节点 $u$ 必须在节点 $v$ 之前执行，$0\le \text{edges.length}\le 100000$。
• s：整数，起始节点编号，$1\le s\le n$。
• t：整数，终止节点编号，$1\le t\le n$。

约束条件：

1. 节点编号从 $1$ 到 $n$ 连续。
2. 依赖关系是单向的，且不存在自依赖（即 $u\ne v$）。
3. 依赖关系构成有向无环图（DAG），保证无循环依赖。

返回值：返回从 $s$ 到 $t$ 的路径总数。

特殊场景：

1. 若 $s=t$，返回 $1$（表示存在一条长度为 $0$ 的路径）。
2. 若从 $s$ 无法到达 $t$，返回 $0$。

输入描述

输入格式如下

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 u,v\le n$、$u\ne v$；
• 依赖关系保证无环；
• $1\le s,t\le n$。

输出描述

输出一行一个十进制整数，表示从 $s$ 到 $t$ 的路径总数。

• 若 $s=t$，输出 1；
• 若从 $s$ 无法到达 $t$，输出 0；
• 数据保证答案不超过 $2^{31}-1$。

样例1

输入

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

输出

2

说明

 1
/ \
2   3
\ /
4

从节点 1 到节点 4 有两条路径：$1\to 2\to 4$ 和 $1\to 3\to 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\to 2\to 4\to 5\to 6$ 和 $1\to 3\to 5\to 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。

题解

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

1. 根据给出的edge建立邻接表，使用拓扑排序处理依赖问题，预处理统计每个节点的入度。
2. 定义dp[i]表示从起点到节点i的路径数量。
3. 初始化dp[s] = 1, 将所有入度为0节点加入队列。
4. 使用BFS进行拓扑排序
   1. 取出队首节点u, 遍历他的所有后继节点v
   2. 更新节点v的路径数，dp[v] += dp[u]
   3. 将 v 的入度减一，如果入度变成 0，加入队列。
5. 最终结果即为dp[t]

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;
}

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/qq_45776114/article/details/170255065