disjoint set, simple solution

  • 0

    disjoint set is simple to understand and easy to implement.

    class Solution {
        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)
            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.