802.找到最终的安全状态

链接：802.找到最终的安全状态
难度：Medium
标签：深度优先搜索、广度优先搜索、图、拓扑排序
简介：返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。

题解 1 - typescript

• 编辑时间：2021-08-05
• 执行用时：204ms
• 内存消耗：53.8MB
• 编程语言：typescript
• 解法介绍：dfs。

function eventualSafeNodes(graph: number[][]): number[] {
  const n = graph.length;
  const ans = new Map<number, boolean>();
  const set = new Set<number>();
  for (let i = 0; i < n; i++) dfs(i);
  function dfs(idx: number) {
    if (set.has(idx)) return false;
    if (ans.has(idx)) return ans.get(idx);
    if (graph[idx].length === 0) {
      ans.set(idx, true);
      return true;
    }
    set.add(idx);
    let f = true;
    for (const next of graph[idx]) {
      if (!dfs(next)) {
        f = false;
        break;
      }
    }
    set.delete(idx);
    ans.set(idx, f);
    return f;
  }
  return [...ans.entries()]
    .filter(([, f]) => f)
    .map(([val]) => val)
    .sort((a, b) => a - b);
}