Diệt tiến trình trong C++

Giới thiệu

Cho n tiến trình, mỗi tiến trình có PID (ID duy nhất) và PPID (ID tiến trình cha). Cấu trúc dạng cây (mỗi tiến trình có 1 cha, gốc có PPID=0). Khi kill 1 tiến trình, tất cả tiến trình con (đệ quy) cũng bị kill. Trả về danh sách PID sẽ bị kill.

Thuật toán: Xây cây + BFS/DFS

1. Xây map children[ppid] = list of pid.
2. BFS từ kill: push vào queue, pop và thêm vào kết quả, push tất cả con.

Cài đặt C++

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

class Solution {
public:
    vector killProcess(vector& pid, vector& ppid, int kill) {
        unordered_map> children;
        int n = pid.size();
        for (int i = 0; i < n; i++) {
            children[ppid[i]].push_back(pid[i]);
        }
        vector res;
        queue q;
        q.push(kill);
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            res.push_back(cur);
            for (int child : children[cur]) q.push(child);
        }
        return res;
    }
};

int main() {
    Solution ob;
    vector pid = {1, 3, 10, 5};
    vector ppid = {3, 0, 5, 3};
    auto ans = ob.killProcess(pid, ppid, 5);
    for (int x : ans) cout << x << ' '; // Output: 5 10
    return 0;
}

Phân tích

• Thời gian: O(N) – mỗi tiến trình xử lý 1 lần.
• Không gian: O(N) – map children + queue.

LeetCode 582 "Kill Process".