题目内容

某文件系统中有 $N$ 个目录，每个目录都有一个独一无二的 $ID$。

每个目录只有一个父目录，但每个父目录下可以有零个或者多个子目录，目录结构呈树状结构。

假设，根目录的 $ID$ 为 $0$，且根目录没有父目录，其他所有目录的 $ID$ 用唯一的正整数表示，并统一编号。

现给定目录 $ID$ 和其父目录 $ID$ 的对应父子关系表 [子目录 $ID$，父目录 $ID$] ，以及一个待删除的目录 $ID$，请计算并返回一个 $ID$ 序列，表示因为删除指定目录后剩下的所有目录，返回的 $ID$ 序列以递增序输出。

注意

1、被删除的目录或文件编号一定在输入的 $ID$ 序列中；

2、当一个目录删除时，它所有的子目录都会被删除。

输入描述

输入的第一行为父子关系表的长度 $m$ ；

接下来的 $m$ 行为 $m$ 个父子关系对；

最后一行为待删除的 $ID$ 。

序列中的元素以空格分割，参见样例。

输出描述

输出一个序列，表示因为删除指定目录后，剩余的目录 $ID$ 。

样例1

输入

5
8 6
10 8
6 0
20 8
2 6
8

输出

2 6

说明

目录结构如下所示：

    6
   / \
  2   8
     / \
    10 20

删除目录 $8$ ，同时它的子目录 $10$ 也被删除，剩余 $2$ 和 $6$ 两个目录。

题解

题面描述

某文件系统中有 $N$ 个目录，每个目录都有一个独一无二的 $ID$。

每个目录只有一个父目录，但每个父目录下可以有零个或者多个子目录，目录结构呈树状结构。

假设，根目录的 $ID$ 为 $0$，且根目录没有父目录，其他所有目录的 $ID$ 用唯一的正整数表示，并统一编号。

现给定目录 $ID$ 和其父目录 $ID$ 的对应父子关系表 [子目录 $ID$，父目录 $ID$]，以及一个待删除的目录 $ID$，请计算并返回一个 $ID$ 序列，表示因为删除指定目录后剩下的所有目录，返回的 $ID$ 序列以递增序输出。

思路

1. 构建树结构：根据给定的父子关系表，构建树的邻接表表示，每个节点存储其子节点列表。
2. 标记删除节点及其子节点：从待删除的节点开始，进行深度优先搜索（DFS）或广度优先搜索（BFS），标记所有需要删除的节点。
3. 收集剩余节点：遍历所有节点，将未被删除的节点ID收集起来。
4. 排序输出：将收集到的节点ID进行排序，并按递增顺序输出。

cpp

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

int main(){
    int m;
    cin >> m;
    // 使用哈希表存储父节点到子节点的映射
    unordered_map<int, vector<int>> tree;
    // 存储所有子节点的ID
    unordered_set<int> all_ids;
    for(int i=0; i<m; ++i){
        int child, parent;
        cin >> child >> parent;
        tree[parent].push_back(child);
        all_ids.insert(child);
    }
    int delete_id;
    cin >> delete_id;
    // 使用队列进行广度优先搜索（BFS）来标记删除的节点
    queue<int> q;
    q.push(delete_id);
    // 使用集合存储所有需要删除的节点
    unordered_set<int> to_delete;
    to_delete.insert(delete_id);
    while(!q.empty()){
        int current = q.front();
        q.pop();
        // 遍历当前节点的子节点
        if(tree.find(current) != tree.end()){
            for(auto &child : tree[current]){
                if(to_delete.find(child) == to_delete.end()){
                    to_delete.insert(child);
                    q.push(child);
                }
            }
        }
    }
    // 收集剩余的节点
    vector<int> remaining;
    for(auto &id : all_ids){
        if(to_delete.find(id) == to_delete.end()){
            remaining.push_back(id);
        }
    }
    // 排序
    sort(remaining.begin(), remaining.end());
    // 输出
    for(int i=0; i<remaining.size(); ++i){
        if(i != 0) cout << " ";
        cout << remaining[i];
    }
    return 0;
}

python

from collections import defaultdict, deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    m = int(data[0])
    tree = defaultdict(list)
    all_ids = set()
    idx = 1
    for _ in range(m):
        child = int(data[idx])
        parent = int(data[idx+1])
        tree[parent].append(child)
        all_ids.add(child)
        idx += 2
    delete_id = int(data[idx])
    # 使用队列进行广度优先搜索（BFS）来标记删除的节点
    q = deque()
    q.append(delete_id)
    to_delete = set()
    to_delete.add(delete_id)
    while q:
        current = q.popleft()
        for child in tree.get(current, []):
            if child not in to_delete:
                to_delete.add(child)
                q.append(child)
    # 收集剩余的节点
    remaining = [id for id in all_ids if id not in to_delete]
    remaining.sort()
    # 输出
    print(' '.join(map(str, remaining)))

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        // 使用哈希表存储父节点到子节点的映射
        Map<Integer, List<Integer>> tree = new HashMap<>();
        // 存储所有子节点的ID
        Set<Integer> allIds = new HashSet<>();
        for(int i=0; i<m; i++){
            int child = sc.nextInt();
            int parent = sc.nextInt();
            tree.computeIfAbsent(parent, k -> new ArrayList<>()).add(child);
            allIds.add(child);
        }
        int deleteId = sc.nextInt();
        // 使用队列进行广度优先搜索（BFS）来标记删除的节点
        Queue<Integer> q = new LinkedList<>();
        q.offer(deleteId);
        Set<Integer> toDelete = new HashSet<>();
        toDelete.add(deleteId);
        while(!q.isEmpty()){
            int current = q.poll();
            if(tree.containsKey(current)){
                for(int child : tree.get(current)){
                    if(!toDelete.contains(child)){
                        toDelete.add(child);
                        q.offer(child);
                    }
                }
            }
        }
        // 收集剩余的节点
        List<Integer> remaining = new ArrayList<>();
        for(int id : allIds){
            if(!toDelete.contains(id)){
                remaining.add(id);
            }
        }
        // 排序
        Collections.sort(remaining);
        // 输出
        for(int i=0; i<remaining.size(); i++){
            if(i != 0) System.out.print(" ");
            System.out.print(remaining.get(i));
        }
    }
}