题目解读

题目要求在一系列补丁版本的迭代关系中，找出迭代（依赖链）次数最多的补丁版本。由于每个版本的前序版本（也就是“依赖它并发布新补丁”的版本）最多只有一个，这就意味着这些版本之间形成了多棵 树结构，每棵树的根节点即没有前序版本（输入中标记为 "NA" 的节点）。

本质问题：
对每棵树，从根节点出发，找出深度最大的叶子节点（即依赖链最长的版本）。如果有多个叶子节点的深度都相同，则按字典序输出所有这些版本。

解题思路

1. 建立树结构：

   • 遍历输入数据，对于每个补丁版本对应的信息，判断它的前序版本是否为 "NA"。
   • 如果是 "NA"，说明这是一个根节点；将其存入一个集合（例如 s）。
   • 否则，以前序版本作为父节点，在字典结构（例如 edge）中保存该前序版本对应的所有后续更新版本（子节点）。

2. 树的遍历与深度统计：

   • 从所有根节点开始，用**深度优先搜索（DFS）**遍历整个树。
   • 每次遍历时传入当前节点和当前深度（从1开始）。
   • 在 DFS 过程中，用两个全局变量来记录：
     • longest：目前为止遍历到的最大深度。
     • res：达到最大深度的所有叶子节点版本（用集合保存，以去重）。
   • 对于每个访问到的节点：
     • 如果当前深度大于 longest，则更新 longest，并清空 res后将当前节点加入。
     • 如果当前深度等于 longest，则直接将当前节点加入 res。

3. 输出结果：

   • 将所有达到最大深度（也就是迭代次数最多）的补丁版本按字典序排序后输出。

代码详解

from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)  # 根据需要设置更高的递归深度

# 读取记录个数
n = int(input())

# 构造一个字典用于存储树的边关系：parent -> [child1, child2, ...]
edge = defaultdict(list)

# 用集合存储所有没有前序版本的版本（即树的根节点）
s = set()

# 读取每一条补丁迭代关系
for i in range(n):
    x, y = input().split()
    if y == "NA":
        # 当前版本没有前序版本，作为一个起始点
        s.add(x)
    else:
        # 记录边关系：y作为前序版本，对应更新的版本包括x
        edge[y].append(x)

# 全局变量，用于记录最大深度和对应的版本集合
longest = 0
res = set()

# DFS函数，用于遍历树并更新最大深度和结果
def dfs(u, dep):
    global longest
    # 当当前节点的深度比已记录的最大深度更大
    if dep > longest:
        longest = dep       # 更新最大深度
        res.clear()         # 清空之前记录的节点
        res.add(u)          # 记录当前节点
    # 如果当前深度与最大深度相同，加入当前节点
    elif dep == longest:
        res.add(u)
    # 递归遍历所有以当前节点为父节点的子节点，深度加1
    for v in edge[u]:
        dfs(v, dep + 1)

# 对每个没有前序版本的节点作为根，进行DFS遍历
for u in s:
    dfs(u, 1)

# 对结果集合按字典序排序后输出
res = sorted(list(res))
print(" ".join(res))

cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>
using namespace std;

// 使用 unordered_map 存储边关系：前序版本 -> 后续版本列表
unordered_map<string, vector<string>> edge;

// 存储所有没有前序版本的根节点
vector<string> roots;

// 全局变量记录最大深度和对应的版本集合
int longest = 0;
vector<string> res;

// DFS 函数：从当前节点 u 开始，当前深度为 depth
void dfs(const string &u, int depth) {
    if (depth > longest) {
        longest = depth;
        res.clear();
        res.push_back(u);
    } else if (depth == longest) {
        res.push_back(u);
    }
    // 遍历所有子节点
    if (edge.find(u) != edge.end()) {
        for (auto &child : edge[u]) {
            dfs(child, depth + 1);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    for (int i = 0; i < n; ++i) {
        string cur, pre;
        cin >> cur >> pre;
        if (pre == "NA") {
            // 没有前序版本，作为树根
            roots.push_back(cur);
        } else {
            // 建立边关系：pre -> cur
            edge[pre].push_back(cur);
        }
    }
    
    // 从所有根节点开始 DFS
    for (auto &root : roots) {
        dfs(root, 1); // 以深度1开始
    }
    
    // 结果按字典序排序输出
    sort(res.begin(), res.end());
    
    bool first = true;
    for (auto &v : res){
        if (!first) cout << " ";
        cout << v;
        first = false;
    }
    cout << "\n";
    return 0;
}

java

import java.util.*;

public class Main {
    // 存储边关系：前序版本 -> 后续版本列表
    static Map<String, List<String>> edge = new HashMap<>();
    // 存储没有前序版本的根节点
    static List<String> roots = new ArrayList<>();
    // 全局变量记录当前最大深度和结果集合
    static int longest = 0;
    static List<String> res = new ArrayList<>();

    // DFS 遍历函数
    public static void dfs(String u, int depth) {
        if (depth > longest) {
            longest = depth;
            res.clear();
            res.add(u);
        } else if (depth == longest) {
            res.add(u);
        }
        // 遍历所有后续版本
        List<String> children = edge.get(u);
        if (children != null) {
            for (String child : children) {
                dfs(child, depth + 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        
        for (int i = 0; i < n; i++) {
            String cur = scanner.next();
            String pre = scanner.next();
            if (pre.equals("NA")) {
                // 当前版本没有前序版本，为根节点
                roots.add(cur);
            } else {
                // 建立前序版本到后续版本的映射关系
                edge.computeIfAbsent(pre, k -> new ArrayList<>()).add(cur);
            }
        }
        scanner.close();
        
        // 从所有根节点开始 DFS 遍历
        for (String root : roots) {
            dfs(root, 1); // 初始深度为1
        }
        
        // 对结果按字典序排序
        Collections.sort(res);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < res.size(); i++) {
            if (i > 0)
                sb.append(" ");
            sb.append(res.get(i));
        }
        System.out.println(sb.toString());
    }
}

题目内容

某测试工具升级时总选择迭代次数最多的补丁版本，已知这些补丁版本的前序版本(即依赖该版本修改发布新补丁版本)，前序版本的个数$<=1$，且不会存在互为前序版本的情况。

请给出最终可以升级的补丁版本。版本号只包含大写字母和数字。

输入描述

第一行为记录的版本迭代关系个数$N$，范围是$[1,100000]$;

第二行到第$N+1$行:每行包含两个字符串，第一个字符串为当前版本，第二个字符串为前序版本，用空格隔开。字符串包含字符个数为$[1,100]$，没有前序版本的第二个字符串固定为$NA$

输出描述

输出所有迭代次数最多的补丁版本号字符串列表，多个版本号以字典序升序排列，用空格隔开

样例1

输入

6
CN0010 BF0001
BF0001 AZ0001
AZ0001 NA
BF0010 AZ0001
AW0001 NA
BF0011 AZ0001

输出

CN0010

说明

$AZ0001$和$AW0001$没有前序版本，各迭代了$0$次；

$BF0001，BF0010$和$BF0011$的前序版本为$AZO001$，各迭代了$1$次;

$CN0010$的前序版本为$BF0001，BF0001$的前序版本为$AZ0001$，迭代了$2$次。

根据要求选择迭代次数最多的补丁版本，因此输出$CN0010$。

样例2

输入

3
BF0001 AZ0001
AZ0001 NA
BF00011 AZ0001

输出

BF0001 BF00011

说明

$AZ0001$没有前序版本，迭代了$0$次;

$BF0001$和$BF00011$的前序版本为$AZ0001$，各迭代了$1$次;

根据要求选择迭代次数最多的补丁版本，有多个版本号时以字典序排列，因此输出$BF0001\ BF00011$