并查集

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/
const int N = 2010;
class UnionFind {
public:
    UnionFind() {
        f.resize(N, 0);
        im.resize(N, 0);
        for (int i = 1; i < N; ++i) {
            f[i] = i;
        }
    }

    int find(int x) {
        return f[x]==x? x: f[x] = find(f[x]);
    }

    void join(int x, int y) {
        int fx = find(x), fy = find(y);
        //if (fx == fy) return;
        f[fy] = fx;
        //im[fx] = im[fx] + im[fy];
    }

    void SetImportance(int x, int importance) {
        im[x] = importance;
    }

    int CountImportance(int id) {
        int res = 0;
        for (int i = 1; i < N; ++i) {
            if (find(i) == id) res += im[i];
        }
        return res;
    }
private:
    vector<int> f;
    vector<int> im;
};


class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        UnionFind ufd;
        for (auto x : employees) ufd.SetImportance(x->id, x->importance);
        for (auto x : employees) {
            if (x->subordinates.empty()) continue;
            for (auto y : x->subordinates) {
                if (y == id) continue;
                ufd.join(x->id, y);
            }
        }
        return ufd.CountImportance(id);
    }
};

dfs

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/
class Solution {
public:
    unordered_map<int, Employee *> mp;

    int dfs(int id) {
        Employee *employee = mp[id];
        int total = employee->importance;
        for (int subId : employee->subordinates) {
            total += dfs(subId);
        }
        return total;
    }

    int getImportance(vector<Employee*> employees, int id) {
        for (auto &employee : employees) {
            mp[employee->id] = employee;
        }
        return dfs(id);
    }
};