Description

Submission

class Solution {
    vector<int> dp;
    vector<vector<int>> graph;
    int n;

    int dfs(int n, vector<int>& quiet) {
        if(dp[n] != -1) return dp[n];
        dp[n] = n;
        for(auto x: graph[n]) {
            if(quiet[dp[n]] > quiet[dp[dfs(x, quiet)]]) dp[n] = dp[x];
        }
        return dp[n];
    }
public:
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
        n = quiet.size();
        dp.resize(n, -1);
        graph.resize(n);

        for(auto& v: richer) {
            graph[v[1]].push_back(v[0]);    // to richer
        }
       
        for(int i = 0; i < n; ++i) {
            dfs(i, quiet);
        }

        return dp;
    }
};