Easy DFS based Solution ✅🏆
Ancestors in a Directed Acyclic Graph (DAG)\n\n## Problem Statement\nGiven a Directed Acyclic Graph (DAG) with n nodes labeled from 0 to n-1, you need to find a
# Ancestors in a Directed Acyclic Graph (DAG)\n\n## Problem Statement\nGiven a Directed Acyclic Graph (DAG) with `n` nodes labeled from `0` to `n-1`, you need to find all the ancestors for each node. An ancestor of a node `j` is a node `i` such that there is a direct or indirect path from `i` to `j`.\n\n## Intuition\nThe first thought is to use Depth-First Search (DFS) to explore all the paths from each node to find its ancestors. We can build a graph representation using an adjacency list and then perform DFS from each node to track its ancestors.\n\n## Approach\n1. **Graph Representation**: Use an adjacency list to represent the graph.\n2. **DFS Traversal**: Perform DFS from each node to find all reachable nodes and mark them as ancestors.\n3. **Tracking Ancestors**: Maintain an answer list where each entry at index `j` will store the ancestors of node `j`.\n4. **Visited Nodes**: Use a visited list to avoid revisiting nodes during DFS to prevent infinite loops.\n\n### Algorithm\n1. Initialize an adjacency list for the graph.\n2. Populate the graph using the given edges.\n3. For each node, initialize a visited list and perform DFS to find all ancestors.\n4. Store the ancestors in the answer list and return the result.\n\n## Complexity\n- **Time complexity**: \\(O(n^2)\\), where `n` is the number of nodes. In the worst case, each node might traverse all other nodes during DFS.\n- **Space complexity**: \\(O(n^2)\\), for storing the graph and the result list.\n\n## Code\n```cpp\nclass Solution {\npublic:\n    void dfs(vector<vector<int>> &graph, int i, int j, vector<vector<int>> &ans, vector<bool> &vis) {\n        vis[j] = true;\n        for (auto &x : graph[j]) {\n            if (!vis[x]) {\n                ans[x].push_back(i);\n                dfs(graph, i, x, ans, vis);\n            }\n        }\n    }\n\n    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> ans(n), graph(n);\n        for (auto &v : edges) {\n            graph[v[0]].push_back(v[1]);\n        }\n        for (int i = 0; i < n; i++) {\n            vector<bool> vis(n);\n            dfs(graph, i, i, ans, vis);\n        }\n        return ans;\n    }\n};\n
['Depth-First Search', 'Breadth-First Search', 'Graph', 'Topological Sort', 'C++']