95% Beats || C++ || DFS on every node
Intuition\nPerform a Depth-First Search (DFS) from each node, and add it to all its descendants through traversal.\n\n# Approach\nWe create an adjacency list ad
# Intuition\nPerform a Depth-First Search (DFS) from each node, and add it to all its descendants through traversal.\n\n# Approach\nWe create an adjacency list `adj` of size $$n$$. Then, we iterate through the edges. Let $$(a, b)$$ be the current edge, then we add $$b$$ to the adjacency list of $$a$$, i.e., `adj[a].add(b)`. Similar to `adj`, we create a list of lists `ans`. We perform DFS from every node. The DFS function takes two arguments `(curr, par)`, denoting the current node and the parent node. For any node $$i$$, the initial call will be `DFS(i, i)`. In the DFS function, we go through the adjacent nodes of `curr` and add `par` as their ancestor.\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n\n- Space complexity: $$O(n^2)$$\n\n# Code\n```\nclass Solution\n{\nprivate:\n    vector<vector<int>> adj, ans;\n    void DFS(int curr, int par)\n    {\n        for (int child : adj[curr])\n        {\n            if (!ans[child].empty() && ans[child].back() == par)\n                continue;\n            ans[child].push_back(par);\n            DFS(child, par);\n        }\n    }\n\npublic:\n    vector<vector<int>> getAncestors(int n, vector<vector<int>> &edges)\n    {\n        adj.resize(n);\n        ans.resize(n);\n        for (vector<int> edge : edges)\n            adj[edge[0]].push_back(edge[1]);\n        for (int i = 0; i < n; i++)\n            DFS(i, i);\n        return ans;\n    }\n};\n```\n# Please Upvote!!!\n\n![image.png](https://assets.leetcode.com/users/images/df44b72f-3410-4242-aafa-20d33e8fe1e7_1702280521.1919644.png)\n\n\n# Beats\n![image.png](https://assets.leetcode.com/users/images/eaa101c1-89b7-4cd4-894a-939a7593d166_1719639383.7915614.png)\n
['Depth-First Search', 'C++']