851.喧闹和富有

链接：851.喧闹和富有
难度：Medium
标签：深度优先搜索、图、拓扑排序、数组
简介：现在，返回一个整数数组 answer 作为答案，其中  answer[x] = y  的前提是，在所有拥有的钱肯定不少于  person x  的人中，person y  是最安静的人（也就是安静值  quiet[y]  最小的人）。

题解 1 - typescript

• 编辑时间：2021-12-15
• 执行用时：216ms
• 内存消耗：49.3MB
• 编程语言：typescript
• 解法介绍：拓扑排序后向下遍历。

class Person {
  parent: Person = this;
  children: Person[] = [];
  constructor(public idx: number, public quiet: number) {}
}
function dfs(list: Set<Person>, persons: Person[], ans: number[]) {
  if (list.size === 0) return;
  const children = new Set<Person>();
  for (const person of list) {
    ans[person.idx] = person.parent.idx;
    for (const child of person.children) {
      children.add(child);
      if (child.parent.quiet > person.parent.quiet) child.parent = person.parent;
    }
  }
  dfs(children, persons, ans);
}
function loudAndRich(richer: number[][], quiet: number[]): number[] {
  const persons = quiet.map((v, i) => new Person(i, v));
  const starts = new Set(persons);
  for (const [i1, i2] of richer) {
    const p1 = persons[i1];
    const p2 = persons[i2];
    p1.children.push(p2);
    starts.delete(p2);
  }
  const ans: number[] = new Array(quiet.length).fill(Infinity);
  dfs(starts, persons, ans);
  return ans;
}