题解 | 2024_网络故障检测_2819

import java.util.*;

public class Main {
    // 自定义设备节点类：存储设备号、类型、端口号、子节点列表
    private static class Node {
        int id;        // 设备号
        int type;      // 0=交换机，1=电脑
        int port;      // 端口号
        List<Node> children; // 下游子设备列表

        // 构造方法：初始化子节点集合，无需外部传参，避免空指针
        public Node(int id, int type, int port) {
            this.id = id;
            this.type = type;
            this.port = port;
            this.children = new ArrayList<>();
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 核心映射：设备号 -> 设备节点，快速查找父节点，O(1)效率
        Map<Integer, Node> deviceMap = new HashMap<>(n);
        Node rootNode = null; // 记录根节点（父设备号=-1的节点）

        for (int i = 0; i < n; i++) {
            int id = sc.nextInt();       // 设备号
            int type = sc.nextInt();     // 类型0/1
            int port = sc.nextInt();     // 端口号
            int fatherId = sc.nextInt(); // 父设备号

            // 创建当前设备节点
            Node curNode = new Node(id, type, port);
            deviceMap.put(id, curNode);

            // 处理父子关系
            if (fatherId == -1) {
                // 父为-1，是根节点
                rootNode = curNode;
            } else {
                // 找到父节点，把当前节点加入父节点的子列表
                Node fatherNode = deviceMap.get(fatherId);
                fatherNode.children.add(curNode);
            }
        }

        // 读取初始故障设备号
        int faultId = sc.nextInt();
        sc.close();

        // 找到故障根节点
        Node faultRoot = deviceMap.get(faultId);
        // 迭代版先序遍历（栈模拟，避免递归栈溢出），收集结果
        List<Integer> res = new ArrayList<>();
        preOrder(faultRoot, res);

        // 按要求输出：设备号以空格分隔一行输出
        for (int i = 0; i < res.size(); i++) {
            if (i > 0) System.out.print(" ");
            System.out.print(res.get(i));
        }
    }

    /**
     * 迭代版先序遍历（推荐，无栈溢出风险，适配1e5数据）
     * @param root 故障根节点
     * @param res  收集遍历的设备号
     */
    private static void preOrder(Node root, List<Integer> res) {
        if (root == null) return;
        Deque<Node> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            res.add(node.id); // 先输出当前节点（先序核心）
            // 栈是后进先出，倒序压入子节点，保证遍历顺序和输入一致
            Collections.reverse(node.children);
            for (Node child : node.children) {
                stack.push(child);
            }
        }
    }

    // 【备选】递归版先序遍历（逻辑简单，适合小数据量，n<1000可用）
    // private static void preOrder(Node root, List<Integer> res) {
    //     if (root == null) return;
    //     res.add(root.id);
    //     for (Node child : root.children) {
    //         preOrder(child, res);
    //     }
    // }
}