C++ O(n) BFS solution using a map only.


  • 0
    G
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        const auto M = pid.size();
        unordered_map<int, vector<int>> m;
        for (auto idx = 0; idx < M; idx++) {
            if (m.find(ppid[idx]) == m.end()) {
                m.emplace(ppid[idx],vector<int>());
            }
            m[ppid[idx]].emplace_back(pid[idx]);
        }
        
        auto idx = 0;
        vector<int> sol;
        sol.emplace_back(kill);
        while (idx < sol.size()) {
            auto cur = sol[idx];
            for (auto&& child : m[cur]) {
                sol.emplace_back(child);
            }
            idx++;
        }
        
        return sol;
    }

Log in to reply
 

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