C++ Solution Using Path Compression


  • 0
    H
    class Solution {
    public:
        vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
            unordered_map<int, int> index;
            vector<int> ans;
            for (int i = 0; i < pid.size(); ++i) {
                index[pid[i]] = i;
            }
            for (int i = 0; i < pid.size(); ++i) {
                ppid[i] = getAncestor(ppid, index, i, kill);
                if (ppid[i] == kill || pid[i] == kill) {
                    ans.push_back(pid[i]);
                }
            }
            return ans;
        }
    
        int getAncestor(vector<int>& parent, unordered_map<int, int>& index, int pos, int kill) {
            if (parent[pos] == 0 || parent[pos] == kill) {
                return parent[pos];
            }
            return (parent[pos] = getAncestor(parent, index, index[parent[pos]], kill));
        }
    };
    

Log in to reply
 

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