C++ (BFS & DFS) + unordered_map


  • 0
    D

    First, build a hash map, indexed by pid, stores the direct children for each process. This will save the search time to O(1), we can directly get the children of a process, no need to go through the entire array.
    Solution one:
    BFS to find the candidates level by level.

    class Solution {
    public:
        vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
            unordered_map<int, vector<int>> hash;
            for(int i = 0; i < ppid.size(); i++){
                hash[ppid[i]].push_back(pid[i]);
            }
            queue<int> que;
            que.push(kill);
            vector<int> proc;
            while(!que.empty()){
                int pp_id = que.front();
                que.pop();
                proc.push_back(pp_id);
                for(int i = 0; i < hash[pp_id].size(); i++){
                    que.push(hash[pp_id][i]);
                }
            }
            return proc;
        }
    };
    

    Solution two: DFS to find the candidates.

    class Solution {
    public:
        vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
            unordered_map<int, vector<int>> hash_table; // <pid, children_set>
            // build hash table which indexed by process ID
            for(int i = 0; i < ppid.size(); i++){
                hash_table[ppid[i]].push_back(pid[i]);
            }
            vector<int> proc;
            proc.push_back(kill);
            find_process_dfs(proc, hash_table, kill);
            return proc;
        }
    private:
        //dfs search
        void find_process_dfs(vector<int>& proc, unordered_map<int, vector<int>>& hash_table, int pid){
            for(auto process : hash_table[pid]){
                proc.push_back(process);
                find_process_dfs(proc, hash_table, process);
            }
            return;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.