DFS
It could be hard to find an efficient solution here. I tried DFS and got TLE, then tried BFS and it got AC. Later, I realized that we can make DFS efficient, an
It could be hard to find an efficient solution here. I tried DFS and got TLE, then tried BFS and it got AC. Later, I realized that we can make DFS efficient, and it is much simpler.\n\nWe first build the adjacency list `al`. Then, we start from each ancestor node ( `anc`), and traverse all children. For each child, we add `anc` to the list of ancestors.\n\nThat way, the list of ancestors will be naturally sorted.\n\n> Note: for each child, we can check if it\'s visited by inspecting it\'s last ancestor. We will get TLE if we do not check if the child has been visited and deduping list of ancestors later.\n\n**C++**\n```cpp\nvector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n    vector<vector<int>> res(n), al(n);\n    function<void(int, int)> dfs = [&](int i, int anc){\n        for (auto j : al[i])\n            if (res[j].empty() || res[j].back() != anc) {\n                res[j].push_back(anc);\n                dfs(j, anc);    \n            }\n    };\n    for (auto &e: edges)\n        al[e[0]].push_back(e[1]);\n    for (int i = 0; i < n; ++i)\n        dfs(i, i);\n    return res;    \n}\n```\n**Complexity Analysis**\n- Time: O(n ^ 2). Traversing DAG from a node is O(n), and we do it for n nodes.\n- Memory:  O(n ^ 2). We can have up to `n ^ 2` edges to store. Also, we need up to `n ^ 2` to store the result.
[]