disjoint set, simple solution


  • 0
    Y

    disjoint set is simple to understand and easy to implement.

    class Solution {
    public:
        vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
            vector<int> results;
            for (int i = 0; i < pid.size(); ++i)
                d[pid[i]] = ppid[i];
            d[kill] = kill;
            d[0] = 0;
            
            for (int id : pid)
                if (parent(id) == kill)
                    results.push_back(id);
            return results;
        }
        
        int parent(int n)
        {
            int p = d[n];
            if (p == n)
                return n;
            return d[n] = parent(p);    // path compression
        }
        
        unordered_map<int, int> d; // disjoint set;
    };
    

Log in to reply
 

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