题面描述

在程序运行过程中，函数调用可能导致栈溢出。给定函数的栈大小和调用关系，判断程序是否会发生栈溢出，并输出相关信息，包括是否溢出、触发溢出的调用路径（如果有）、以及栈的最大消耗。如果没有溢出，则输出最大栈消耗的调用路径。输入包括函数数量、每个函数的栈大小、调用关系和系统最大栈空间，输出需提供三项信息，确保正确识别栈的使用情况。

思路

简化来说，这个问题本质上是一个有向无环图（DAG）中的路径最大权值问题，主要关注的是如何判断路径的栈消耗是否超过系统允许的最大空间。

1. 图结构与路径搜索：

   • 这个问题可以看作是从入口函数出发的一种路径搜索问题，其中每条路径代表一个调用链。
   • 图中每个节点（函数）有一个权值（栈大小），而路径上的累加权值即为路径的总栈消耗。
   • 关键是找到所有从入口到叶子的调用路径，并计算其栈消耗。

2. 栈溢出的检测条件：

   • 对于每条路径，计算其栈消耗并与系统最大栈空间进行比较。
   • 如果某条路径上的栈消耗超过系统配置的最大栈空间，则认为出现了栈溢出，且只需找到第一条导致栈溢出的路径即可，因为后续路径已经无关紧要。

3. 最大栈消耗路径：

   • 如果不存在栈溢出，则我们要寻找占用最大栈空间的路径（路径栈消耗最高的路径），这就需要记录所有路径的栈消耗值，并返回其中最大的一条。
   • 这种情况下，我们找到的就是调用链中消耗栈空间最多的一条路径。

4. 无递归的简化：

   • 由于题目保证没有递归调用，所以它是一个DAG，这使得问题在递归遍历过程中不会进入死循环，能顺利完成所有路径的计算。

具体分析

完整思路

1. 解析输入数据：

   • 首先我们读取输入的函数数量及每个函数对应的栈大小。这一步的目的是将每个函数的栈消耗大小映射到一个字典或哈希表中（如 C++ 中的 unordered_map 或 Java 中的 HashMap）。
   • 然后，我们读取函数的调用关系，将这些调用关系表示为有向图。图的结构可以通过邻接表的形式存储，使用字典，键为调用函数，值为其调用的子函数列表。

2. 构建调用图：

   • 每个函数的调用关系表示为有向边（调用方到被调用方）。例如，如果函数 A 调用了 B 和 C，则会有两条边：A->B 和 A->C。
   • 需要特别注意调用顺序和递归问题。题目中已经说明不会有递归调用，所以不需要检测图中的环，处理有向无环图（DAG）即可。

3. 深度优先搜索 (DFS)：

   • 起点：从主函数开始，进行深度优先遍历。主函数可以通过读取调用关系的第一个函数作为入口点。
   • 状态跟踪：在遍历过程中，我们需要跟踪当前栈空间的使用情况，以及当前的调用路径。
     • 对每个函数调用时，将当前函数的栈大小累加到当前栈空间，并将该函数加入当前路径。
   • 判断溢出：在每次累加栈空间后，检查当前栈消耗是否超出系统配置的最大栈空间。如果超出了限制，标记为栈溢出，并记录导致溢出的调用路径和栈使用量。此时可以立即停止该条路径的进一步递归，因为后续不会再有更优解。
   • 路径终止：如果当前函数没有更多子函数调用（即到达叶子节点），我们需要检查当前路径是否是栈空间消耗最大的路径。如果是，则更新最大栈消耗和对应的路径。
   • 回溯：递归返回时，要从当前路径中移除已经访问的节点（函数），继续搜索其他路径。

4. 判断和输出：

   • 发生溢出的情况：一旦检测到栈溢出，记录发生溢出的路径和栈消耗。根据题目要求，只输出第一次栈溢出的情况，不再继续其他路径的探索。
   • 没有发生溢出的情况：如果整个搜索结束后没有栈溢出，那么返回整个图中消耗栈空间最多的路径及其消耗量。

5. 时间和空间复杂度：

   • 时间复杂度：由于需要遍历整个调用图的所有路径，时间复杂度大致为 $O(N + M)$，其中 $N$ 是函数数量，$M$ 是调用关系数量。
   • 空间复杂度：除了输入数据占用的空间外，还需要存储当前路径（长度最多为 $N$），因此空间复杂度为 $O(N + M)$。

Python

# 读取函数个数 N
N = int(input())

# 初始化一个字典 space_map，用于存储每个函数的栈空间大小
space_map = {}

# 遍历输入 N 次，获取每个函数的名称和对应的栈空间
for i in range(N):
    fun_name , space = input().split()  # 读取函数名称和栈空间
    space_map[fun_name] = int(space)    # 将栈空间转为整数并存储在字典中

# 初始化一个字典 edge，用于存储每个函数的调用关系
edge = {}

# 读取函数调用关系的数量 m
m = int(input())

# 定义 main_func 为空字符串，用于记录主函数名称
main_func = ''

# 遍历输入 m 次，获取函数调用关系
for _ in range(m):
    line = input().split()  # 读取一行调用关系
    if main_func == '':      # 如果 main_func 为空，则将第一个函数作为主函数
        main_func = line[0]
    root = line[0]           # 调用方函数
    sons = line[1:]          # 被调用的函数列表
    edge[root] = sons        # 存储调用关系，key 为调用方，value 为被调用函数列表

# 读取系统的栈空间限制
space_limit = int(input())

# 初始化用于记录栈溢出的路径、溢出时的栈空间、最大消耗栈空间和最大路径
stop_path = []    # 记录发生栈溢出的路径
stop_space = 0    # 记录发生栈溢出时的栈空间
max_space = 0     # 记录最大栈消耗
max_path = []     # 记录最大消耗栈空间的路径
cur_path = []     # 记录当前递归中的路径

# 定义一个深度优先搜索 (DFS) 函数
def dfs(node, cur_space):
    global space_limit, stop_path, stop_space, max_space, max_path, cur_path
    cur_path.append(node)  # 当前函数加入路径

    # 如果当前路径的栈空间已经超过系统限制，记录溢出路径和栈空间
    if cur_space > space_limit:
        stop_path = cur_path.copy()  # 复制当前路径为溢出路径
        stop_space = cur_space       # 记录溢出的栈空间
        return True  # 返回 True 表示栈溢出

    # 如果当前函数没有子函数调用，即为叶子节点
    if node not in edge:
        # 如果当前路径的栈消耗大于目前记录的最大栈空间，更新最大栈空间和路径
        if cur_space > max_space:
            max_path = cur_path.copy()  # 复制当前路径为最大栈路径
            max_space = cur_space       # 更新最大栈消耗
        cur_path.pop()  # 回溯，移除当前函数
        return False    # 返回 False 表示没有栈溢出

    # 遍历当前函数的所有被调用函数（子节点）
    for son in edge[node]:
        stop_flag = dfs(son, cur_space + space_map[son])  # 递归调用下一个函数，并累加栈空间
        if stop_flag:  # 如果下层递归返回 True，表示发生栈溢出，停止递归
            return True
    cur_path.pop()  # 如果没有栈溢出，回溯，移除当前函数

# 从主函数开始进行深度优先搜索，初始栈空间为主函数的栈空间
dfs(main_func, space_map[main_func])

# 定义输出结果的变量
flag = ""         # 记录是否栈溢出
path_str = ""     # 记录路径的字符串形式
final_space = 0   # 记录最终的栈消耗

# 如果 stop_space 为 0，表示没有栈溢出
if stop_space == 0:
    flag = "false"                        # 设置 flag 为 false，表示没有栈溢出
    path_str = "-".join(max_path)         # 路径字符串为最大栈消耗路径
    final_space = max_space               # 栈消耗为最大栈空间
else:
    flag = "true"                         # 设置 flag 为 true，表示发生了栈溢出
    path_str = "-".join(stop_path)        # 路径字符串为栈溢出的路径
    final_space = stop_space              # 栈消耗为溢出的栈空间

# 输出结果，格式为：是否栈溢出 路径 栈消耗
print(flag, path_str, final_space)

java

import java.util.*;

public class StackOverflowDetection {
    // 用于存储每个函数的栈空间大小
    static Map<String, Integer> spaceMap = new HashMap<>();
    // 用于存储每个函数的调用关系
    static Map<String, List<String>> edge = new HashMap<>();
    static String mainFunc = "";
    static List<String> stopPath = new ArrayList<>();
    static int stopSpace = 0;
    static int maxSpace = 0;
    static List<String> maxPath = new ArrayList<>();
    static List<String> curPath = new ArrayList<>();
    static int spaceLimit;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取函数个数 N
        int N = Integer.parseInt(scanner.nextLine());

        // 初始化栈空间
        for (int i = 0; i < N; i++) {
            String[] input = scanner.nextLine().split(" ");
            String funName = input[0];
            int space = Integer.parseInt(input[1]);
            spaceMap.put(funName, space);
        }

        // 读取函数调用关系的数量 m
        int m = Integer.parseInt(scanner.nextLine());

        // 读取函数调用关系
        for (int i = 0; i < m; i++) {
            String[] line = scanner.nextLine().split(" ");
            if (mainFunc.isEmpty()) {
                mainFunc = line[0];
            }
            String root = line[0];
            List<String> sons = Arrays.asList(Arrays.copyOfRange(line, 1, line.length));
            edge.put(root, sons);
        }

        // 读取系统的栈空间限制
        spaceLimit = Integer.parseInt(scanner.nextLine());

        // 从主函数开始进行深度优先搜索
        dfs(mainFunc, spaceMap.get(mainFunc));

        // 输出结果
        String flag;
        String pathStr;
        int finalSpace;

        if (stopSpace == 0) {
            flag = "false";
            pathStr = String.join("-", maxPath);
            finalSpace = maxSpace;
        } else {
            flag = "true";
            pathStr = String.join("-", stopPath);
            finalSpace = stopSpace;
        }

        // 输出结果
        System.out.println(flag + " " + pathStr + " " + finalSpace);
    }

    // 定义深度优先搜索 (DFS) 函数
    static boolean dfs(String node, int curSpace) {
        curPath.add(node); // 当前函数加入路径

        // 如果当前路径的栈空间超过系统限制，记录溢出路径和栈空间
        if (curSpace > spaceLimit) {
            stopPath = new ArrayList<>(curPath); // 复制当前路径为溢出路径
            stopSpace = curSpace; // 记录溢出的栈空间
            return true; // 返回 true 表示栈溢出
        }

        // 如果当前函数没有子函数调用，即为叶子节点
        if (!edge.containsKey(node)) {
            if (curSpace > maxSpace) {
                maxPath = new ArrayList<>(curPath); // 复制当前路径为最大栈路径
                maxSpace = curSpace; // 更新最大栈消耗
            }
            curPath.remove(curPath.size() - 1); // 回溯，移除当前函数
            return false; // 返回 false 表示没有栈溢出
        }

        // 遍历当前函数的所有被调用函数（子节点）
        for (String son : edge.get(node)) {
            boolean stopFlag = dfs(son, curSpace + spaceMap.get(son)); // 递归调用下一个函数，并累加栈空间
            if (stopFlag) { // 如果下层递归返回 true，表示发生栈溢出，停止递归
                return true;
            }
        }
        curPath.remove(curPath.size() - 1); // 如果没有栈溢出，回溯，移除当前函数
        return false;
    }
}

题目内容

代码运行过程，经常会出现栈溢出情况，现给定函数调用关系和每个函数的栈大小，判断该程序是否存在栈溢出的风险。

如程序如下：

A()

{

    B()；

    C()；

}

B()

{

​    D();

}

C()

{

    E();

}

其中$A、B、C、D、E$的为函数。$A$调用了$B、C$;$B$调用了$D;C$调用了$E$。如果每个函数独立的栈大小分别为:$A$为$10$(不包括$B、C$的栈大小),$B$为$20$，$C$为$5$，$D$为$15$，$E$为$50$。调用过程中最大栈空间为路径为$A>C>E$,最大栈空间为$65$($A->B->D$的路径调用最大栈空间为$45$)，如果整体系统最大额定栈空间配置为$60$，则$A->C->E$调用执行时会出现栈溢出异常。

说明

1.函数名称为单个大写字母,最大不超过$26$个函数

2.调用栈为正整数;

3.调用关系不会出现递归调用

4.最大消耗的栈空间等于系统设定的最大空间，不会发生溢出。只有大于系统最大空间，才发生溢出。

输入描述

输入包括三个信息:每个函数的独立栈大小，函数调用关系，系统配置的最大栈空间。格式如下:

第一行:数字$N$，代表有$N$个函数，

第二行到$N+1$行4表示每个函数名称和栈大小，空格隔开。

第$N+2$行: 数字$M$，代表下面$M$行的函数直接调用关系，第一个字母表示调用函数，后面的字母表示被调用函数，并且是按序调用。如$ABC$表示先$A->B$，然后$A->C$(如示例所示)

最后一行:数字$K$，代表系统配置的最大栈空间

说明:假设主函数都是从第一个调用关系开始发起调用(数字M之后的第一行中第一个函数可以认为是主函数调用口)，不会从中间某个函数开始调用

输出描述

输出信息包括:

1.是否会出现栈溢出，

2.如果栈溢出，则输出发生栈溢出的调用路径(路径只输出到触发栈溢出的函数);如果没有栈溢出，则输出最大消耗栈的调用路径(如果存在相同大小的调用路径，输出第一个)

3.如果栈溢出，输出发生栈溢出时调用关系的栈大小，如果没有栈溢 出，输出最大栈消耗

三个信息一行打印，中间空格隔开;如果栈溢出，只输出第一次触发栈溢出时的调用关系即可(实际上如果发生了栈溢出，系统也会异常，不会继续产生后续调用了)。

样例1

输入

6
A 20
B 10
C 5
D 15
E 50
F 60
3
A B C
B D 
C E F 
70

输出

true A-C-E 75

说明

给定输入，第一个调用关系为A BC，则A为入口函数，先执行A-B-D调用，对应占空间为45，当执行到A-C-E时，超过了70，触发了栈溢出。不会再触发函数C调用函故F了，所以输出为A-C-E，对应的栈空间为75

样例2

输入

6
A 20
B 10
C 5
D 15
E 50
F 60
3 
A B C
B D
C E F
100

输出

false A-C-F 85

说明

该示例中，最大占空间配置为100，可以调用完所有函数，不会发生栈溢出，最大调用栈调用关系为A-C-F，消耗的最大栈空间为85