582. 杀掉进程 🔒

难度中等

题目描述

系统中存在 n 个进程，形成一个有根树结构。给你两个整数数组 pid 和 ppid ，其中 pid[i] 是第 i 个进程的 ID ，ppid[i] 是第 i 个进程的父进程 ID 。

每一个进程只有 一个父进程 ，但是可能会有 一个或者多个子进程 。只有一个进程的 ppid[i] = 0 ，意味着这个进程 没有父进程 。

当一个进程 被杀掉 的时候，它所有的子进程和后代进程都要被杀掉。

给你一个整数 kill 表示要杀掉进程的 ID ，返回被杀掉的进程的 ID 列表。可以按 任意顺序 返回答案。

示例 1：

输入：pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5
输出：[5,10]
解释：涂为红色的进程是应该被杀掉的进程。

示例 2：

输入：pid = [1], ppid = [0], kill = 1
输出：[1]

提示：

n == pid.length
n == ppid.length
1 <= n <= 5 * 10⁴
1 <= pid[i] <= 5 * 10⁴
0 <= ppid[i] <= 5 * 10⁴
仅有一个进程没有父进程
pid 中的所有值 互不相同
题目数据保证 kill 在 pid 中

解法

方法一：DFS

思考

杀掉一个进程会杀掉它的整棵子进程树。父子关系由两个平行数组给出，宜先建成邻接表。

\(g[p]\) 存 \(p\) 的孩子。从 kill 出发 DFS/BFS，沿子边收集全部节点。每个进程至多进入一次。

我们先根据 \(pid\) 和 \(ppid\) 构建出图 \(g\)，其中 \(g[i]\) 表示进程 \(i\) 的所有子进程。然后从进程 \(kill\) 开始，进行深度优先搜索，即可得到所有被杀掉的进程。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是进程的数量。

Python3JavaC++GoTypeScriptRust

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        def dfs(i: int):
            ans.append(i)
            for j in g[i]:
                dfs(j)

        g = defaultdict(list)
        for i, p in zip(pid, ppid):
            g[p].append(i)
        ans = []
        dfs(kill)
        return ans

class Solution {
    private Map<Integer, List<Integer>> g = new HashMap<>();
    private List<Integer> ans = new ArrayList<>();

    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        int n = pid.size();
        for (int i = 0; i < n; ++i) {
            g.computeIfAbsent(ppid.get(i), k -> new ArrayList<>()).add(pid.get(i));
        }
        dfs(kill);
        return ans;
    }

    private void dfs(int i) {
        ans.add(i);
        for (int j : g.getOrDefault(i, Collections.emptyList())) {
            dfs(j);
        }
    }
}

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        unordered_map<int, vector<int>> g;
        int n = pid.size();
        for (int i = 0; i < n; ++i) {
            g[ppid[i]].push_back(pid[i]);
        }
        vector<int> ans;
        function<void(int)> dfs = [&](int i) {
            ans.push_back(i);
            for (int j : g[i]) {
                dfs(j);
            }
        };
        dfs(kill);
        return ans;
    }
};

func killProcess(pid []int, ppid []int, kill int) (ans []int) {
    g := map[int][]int{}
    for i, p := range ppid {
        g[p] = append(g[p], pid[i])
    }
    var dfs func(int)
    dfs = func(i int) {
        ans = append(ans, i)
        for _, j := range g[i] {
            dfs(j)
        }
    }
    dfs(kill)
    return
}

function killProcess(pid: number[], ppid: number[], kill: number): number[] {
    const g: Map<number, number[]> = new Map();
    for (let i = 0; i < pid.length; ++i) {
        if (!g.has(ppid[i])) {
            g.set(ppid[i], []);
        }
        g.get(ppid[i])?.push(pid[i]);
    }
    const ans: number[] = [];
    const dfs = (i: number) => {
        ans.push(i);
        for (const j of g.get(i) ?? []) {
            dfs(j);
        }
    };
    dfs(kill);
    return ans;
}

use std::collections::HashMap;

impl Solution {
    pub fn kill_process(pid: Vec<i32>, ppid: Vec<i32>, kill: i32) -> Vec<i32> {
        let mut g: HashMap<i32, Vec<i32>> = HashMap::new();
        let mut ans: Vec<i32> = Vec::new();

        let n = pid.len();
        for i in 0..n {
            g.entry(ppid[i]).or_insert(Vec::new()).push(pid[i]);
        }

        Self::dfs(&mut ans, &g, kill);
        ans
    }

    fn dfs(ans: &mut Vec<i32>, g: &HashMap<i32, Vec<i32>>, i: i32) {
        ans.push(i);
        if let Some(children) = g.get(&i) {
            for &j in children {
                Self::dfs(ans, g, j);
            }
        }
    }
}

方法二：显式栈

思考

杀掉一个进程会把它的全部后代一起杀掉。父子关系由两个平行数组给出， \(n\) 最大为 \(5 \times 10^4\)，先建成每个进程的子进程列表更方便遍历。沿一条父子链递归收集时，调用深度等于进程数，链长达到 \(1000\) 就会超出 Python 的递归上限。因此用栈保存待访问的进程：弹出时记入答案，再把子进程按相反顺序压入，收集顺序就与沿子列表的先序遍历相同。树没有环，每个进程只入栈一次。

先根据 \(pid\) 和 \(ppid\) 建图， \(g[i]\) 表示进程 \(i\) 的所有子进程。从进程 \(kill\) 开始用显式栈遍历。弹出进程 \(i\) 时把它加入答案，再把它的子进程按相反顺序压入栈，这样后弹出的是子列表中靠前的进程。每个后代都会被收集一次。题目允许按任意顺序返回答案。