Задача: 851. Loud and Rich
Сложность: medium

Есть группа из n человек, пронумерованных от 0 до n - 1, где у каждого человека разное количество денег и разный уровень спокойствия.

Вам дан массив richer, где richer[i] = [ai, bi] указывает на то, что ai имеет больше денег, чем bi, и целочисленный массив quiet, где quiet[i] — это уровень спокойствия i-го человека. Все данные в richer логически корректны (т.е. данные не приведут к ситуации, где x богаче y и y богаче x одновременно).

Верните целочисленный массив answer, где answer[x] = y, если y — это самый спокойный человек (то есть человек y с наименьшим значением quiet[y]) среди всех людей, которые однозначно имеют столько же или больше денег, чем человек x.

Пример:

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but it is not clear if they have more money than person 0.
answer[7] = 7.
Among all people that definitely have equal to or more money than person 7 (which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x]) is person 7.
The other answers can be filled out with similar reasoning.

👨‍💻 Алгоритм:

1⃣Постройте граф, описанный выше, и пусть dfs(person) будет самым спокойным человеком в поддереве person. Обратите внимание, что из-за логической последовательности утверждений граф должен быть DAG — ориентированным графом без циклов.

2⃣Теперь dfs(person) — это либо сам person, либо min(dfs(child) для каждого child из person). То есть, самый спокойный человек в поддереве — это либо сам person, либо самый спокойный человек в каком-то поддереве потомка person.

3⃣Мы можем кэшировать значения dfs(person) в answer[person], выполняя обход графа в пост-обходе. Таким образом, мы не повторяем работу. Этот метод уменьшает квадратичное время выполнения алгоритма до линейного.

😎 Решение:

class Solution {
    ArrayList<Integer>[] graph;
    int[] answer;
    int[] quiet;

    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int N = quiet.length;
        graph = new ArrayList[N];
        answer = new int[N];
        this.quiet = quiet;

        for (int node = 0; node < N; ++node)
            graph[node] = new ArrayList<Integer>();

        for (int[] edge: richer)
            graph[edge[1]].add(edge[0]);

        Arrays.fill(answer, -1);

        for (int node = 0; node < N; ++node)
            dfs(node);
        return answer;
    }

    public int dfs(int node) {
        if (answer[node] == -1) {
            answer[node] = node;
            for (int child: graph[node]) {
                int cand = dfs(child);
                if (quiet[cand] < quiet[answer[node]])
                    answer[node] = cand;
            }
        }
        return answer[node];
    }
}

Ставь 👍 и забирай 📚 Базу знаний