Kill Process – ลบกระบวนการและลูกใน C++

ปัญหา: Kill Process

มีกระบวนการ n ตัว แต่ละตัวมี PID (ID) และ PPID (Parent PID)
โครงสร้างเป็น Tree (มี root เดียวที่ PPID=0)
Kill PID หนึ่ง → ลูกทั้งหมดก็ตายตาม → หา รายการ PID ที่จะถูก kill

ตัวอย่าง

pid = [1, 3, 10, 5], ppid = [3, 0, 5, 3], kill = 5
Tree: 3 → {1, 5}, 5 → {10}
Kill 5 → ตาย: [5, 10]

แนวทางแก้ปัญหา: Build Tree + BFS/DFS

ขั้นตอน

1. สร้าง Adjacency List: children[parent].push_back(child)
2. BFS/DFS จาก kill → เก็บ PID ทุกตัวที่เยี่ยม

ตัวอย่างโค้ด C++

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

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        unordered_map<int, vector<int>> children;
        int n = pid.size();

        for (int i = 0; i < n; i++)
            children[ppid[i]].push_back(pid[i]);

        vector<int> result;
        queue<int> q;
        q.push(kill);

        while (!q.empty()) {
            int curr = q.front(); q.pop();
            result.push_back(curr);
            for (int child : children[curr])
                q.push(child);
        }
        return result;
    }
};

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

DFS Version (Recursive)

void dfs(int node, unordered_map<int, vector<int>>& children, vector<int>& res) {
    res.push_back(node);
    for (int child : children[node])
        dfs(child, children, res);
}

ความซับซ้อน

• เวลา: O(N) – สร้าง graph + traverse
• พื้นที่: O(N) – adjacency list + queue/stack

ข้อสังเกต

• LeetCode 582
• ใช้ unordered_map เพราะ PID อาจไม่ได้เรียงติดกัน
• BFS และ DFS ให้ผลลัพธ์เหมือนกัน (แต่ลำดับอาจต่างกัน – โจทย์ไม่กำหนดลำดับ)
• Tree height อาจใหญ่ → BFS ปลอดภัยกว่า stack overflow