582. Kill Process

Posted on Edited on In

582. Kill Process

Description

You have n processes forming a rooted tree structure. You are given two integer arrays pid and ppid, where pid[i] is the ID of the i^th process and ppid[i] is the ID of the i^th process’s parent process.

Each process has only one parent process but may have multiple children processes. Only one process has ppid[i] = 0, which means this process has no parent process (the root of the tree).

When a process is killed, all of its children processes will also be killed.

Given an integer kill representing the ID of a process you want to kill, return a list of the IDs of the processes that will be killed. You may return the answer in any order.

Example 1:

1
2
3
Input: pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5
Output: [5,10]
Explanation:The processes colored in red are the processes that should be killed.

Example 2:

1
2
Input: pid = [1], ppid = [0], kill = 1
Output: [1]

Constraints:

  • n == pid.length
  • n == ppid.length
  • 1 <= n <= 5 * 10^4
  • 1 <= pid[i] <= 5 * 10^4
  • 0 <= ppid[i] <= 5 * 10^4
  • Only one process has no parent.
  • All the values of pid are unique .
  • kill is guaranteed to be in pid.

Hints/Notes

  • dfs

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> res;
    map<int, vector<int>> m;

    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        int n = pid.size(), root = -1;
        for (int i = 0; i < n; i++) {
            int p = pid[i];
            int pp = ppid[i];
            if (pp == 0) {
                root = p;
            } else {
                m[pp].push_back(p);
            }
        }
        traverse(kill);
        return res;
    }

    void traverse(int root) {
        res.push_back(root);
        for (int child : m[root]) {
            traverse(child);
        }
    }
};