[JavaScript] Easy to understand - 3 solutions - detailed explanation
Base Information\n\nIt\'s a DAG, and we have all the edges, which means we also have these information:\n- the indegree for each node, let\'s call them array in
## Base Information\n\nIt\'s a DAG, and we have all the edges, which means we also have these information:\n- the indegree for each node, let\'s call them array `indegrees`\n- the outdegree for each node, let\'s call them array `outdegrees`\n- all the nodes that link to current node, let\'s call them array `inEdges`\n- all the nodes that current node linked to, let\'s call them array `outEdges`\n\nBased on these information, let\'s move into the 3 solutions.\n\n## BFS\n\nLet\'s see what is a node with 0 indegree.\n\n![image](https://assets.leetcode.com/users/images/f91f9cd8-58c0-4b5b-8064-fc8ac072c803_1646791992.766624.png)\n\nWith this test case, it\'s the nodes `0`, `1` and `2` at first. And since there\'s no extra income edges, which means we\'ve get the final result for these nodes already. Let\'s call them the level 0.\n\nThen, for all the out edges from level 0, which are `3`, `4` and `7`, let\'s update their indegree. Take the node `3` as an example:\n- the first income edge is `[0, 3]`, so we could add all the income edges of `0` into the income edges of `3`, which is merging `inEdges[0]` into `inEdges[3]`. After this, we\'ve handled this edge fine, so we could do the `--indegree[3]` to assume there\'s no such edge.\n- then, we do the same things to the second edge `[1, 3]`.\n- finally, the node `3` is a new node with 0 indegree.\n\nLet\'s finish all the things for the edges `3`, `4` and `7`. And then, we could get a new batch of nodes with 0 indegree, which are `3` and `4`. Let\'s call them the level 1.\n\nThen, for all the out edges from level 1, we continue to do the same things above. We can get the level 2, level 3 and so on. Until there\'s no node for the next level, which means we get all the results we want.\n\nFinally, let\'s look back the whole strategy, it\'s just like we get deeper level by level from the start. So, it\'s a classic BFS strategy.\n\nHere\'s a sample code from me:\n\n```js\n// BFS\nconst getAncestors = (n, edges) => {\n  const indegrees = new Uint16Array(n);\n  const inEdges = Array.from({ length: n }, () => new Set());\n  const outEdges = Array.from({ length: n }, () => []);\n  let curLevel = [];\n  // init information\n  for (const [from, to] of edges) {\n    ++indegrees[to];\n    inEdges[to].add(from);\n    outEdges[from].push(to);\n  }\n  // init level 0\n  for (let i = 0; i < n; ++i) {\n    indegrees[i] === 0 && curLevel.push(i);\n  }\n  // geting deeper level by level\n  while (curLevel.length) {\n    const next = [];\n    for (const i of curLevel) {\n      for (const out of outEdges[i]) {\n        --indegrees[out] === 0 && next.push(out);\n        for (const edge of inEdges[i]) {\n          inEdges[out].add(edge);\n        }\n      }\n    }\n    curLevel = next;\n  }\n  return inEdges.map(set => Array.from(set).sort((a, b) => a - b));\n};\n```\n\n## DFS - bottom top\n\nLet\'s see how to get the final result for one node.\n\n![image](https://assets.leetcode.com/users/images/f91f9cd8-58c0-4b5b-8064-fc8ac072c803_1646791992.766624.png)\n\nWith this test case again, let\'s take node `5` as an example:\n- what\'s the final result for node `5`\n\t- it comes from node `3` and the final result of node `3`\n\t- what\'s the final result for node `3`\n\t\t- it comes from node `0`, the final result of node `0`, node `1`, and the final result of node `1`\n\t\t\t- what\'s the final result for node `0`\n\t\t\t\t- empty\n\t\t\t- what\'s the final result for node `1`\n\t\t\t\t- empty\n\nWe could find out that we are dealing with the same kind of problem for different node again and again, until meets the end condition. That\'s a classic recursive strategy.\n\nSo, for the whole problem, we just need to deal with all the leaf nodes as the start of recursion, then we could get the final answer.\n\nHere\'s a sample code from me:\n\n```js\n// DFS - bottom top\nconst dfs = (inEdges, idx, finished) => {\n  if (finished[idx]) return; // avoid repeat calculation\n  if (inEdges[idx].size === 0) return; // end condition\n  for (const edge of inEdges[idx]) {\n    dfs(inEdges, edge, finished); // move up\n    inEdges[idx] = new Set([...inEdges[idx], ...inEdges[edge]]); // merge\n  }\n  finished[idx] = 1;\n};\nconst getAncestors = (n, edges) => {\n  const inEdges = Array.from({ length: n }, () => new Set());\n  const outdegrees = new Uint16Array(n);\n  const finished = new Uint8Array(n);\n  // init information\n  for (const [from, to] of edges) {\n    inEdges[to].add(from);\n    ++outdegrees[from];\n  }\n  for (let i = 0; i < n; ++i) {\n\t// start dfs from every leaf node\n    outdegrees[i] == 0 && dfs(inEdges, i, finished);\n  }\n  return inEdges.map(set => Array.from(set).sort((a, b) => a - b));\n};\n```\n\n## DFS - top bottom\n\nLet\'s see how we can handle all the effects of a node on the final result.\n\n![image](https://assets.leetcode.com/users/images/f91f9cd8-58c0-4b5b-8064-fc8ac072c803_1646791992.766624.png)\n\nWith this test case again again, haha, let\'s take node `0` as an example. In the final result, the nodes `3`, `4`, `5`, `6` and `7` will be effected by node `0`. Let\'s look at these nodes individually, actually it\'s just a tree with the root node `0`. So we could traverse the tree by DFS easily to add the `0` to the result of each node.\n\nThen we do the same things for each node, so we could get the final result.\n\nHere\'s a sameple code from me:\n\n```js\n// DFS - top bottom\nconst dfs = (inEdges, outEdges, originValue, curValue, finished) => {\n  if (finished[curValue]) return; // avoid repeat calculation\n  finished[curValue] = 1;\n  for (const out of outEdges[curValue]) {\n    inEdges[out].add(originValue);\n    dfs(inEdges, outEdges, originValue, out, finished); // traverse tree\n  }\n};\nconst getAncestors = (n, edges) => {\n  const inEdges = Array.from({ length: n }, () => new Set());\n  const outEdges = Array.from({ length: n }, () => []);\n  // init information\n  for (const [from, to] of edges) {\n    inEdges[to].add(from);\n    outEdges[from].push(to);\n  }\n  for (let i = 0; i < n; ++i) {\n\t// start dfs from each node as the root\n    dfs(inEdges, outEdges, i, i, new Uint8Array(n));\n  }\n  return inEdges.map(set => Array.from(set).sort((a, b) => a - b));\n};\n```
['JavaScript']