Idea Explained and optimization || DFS based approach || C++ Clean Code
Intuition :\n\n Idea here is to store nodes in adjacency list by reversing edges. \n\n\t i.e if we have [ u -> v ], then we store this in adjacency list as  [ v
**Intuition :**\n\n* Idea here is to store nodes in adjacency list by **reversing edges.** \n\n\t* i.e if we have **[ u -> v ],** then we store this in adjacency list as  **[ v -> u ]**\n* In simple terms instead of connecting **parent -> child**, connect **child -> parent**\n* So, in this way we can easily get all the ancestors of a node by simply doing **DFS**.\n* Then perform simple DFS for each node from 0 to n-1.\n* And in DFS call we store the nodes that are reachable from source node.\n* In the end we sort all reachable nodes as mentioned in problem.\n\n# Code :\n\n```\nclass Solution {\nprivate:\n\tvoid dfs(vector<vector<int>>& adj, vector<vector<int>>& res, vector<bool>& vis, int node, int source) {\n        vis[node] = true;\n\t\t// If current node is not source then \n\t\t// add current node to list of ancestor of source node\n        if(node != source) \n            res[source].push_back(node);\n\t\t\n\t\t// Iterate over adjacent nodes and perform dfs \n\t\t// to include ancestors \n        for(auto& adjnode : adj[node]) {\n            if(!vis[adjnode]) {\n                dfs(adj, res, vis, adjnode, source);\n            }\n        }\n    }\n\t\npublic:\n    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        \n        vector<vector<int>> adj(n); // adjacency list\n        vector<vector<int>> res(n); // List to store all ancestors of each node\n        \n        for(auto& edge : edges) {\n\t\t\t// Connect child -> parent\n            adj[edge[1]].push_back(edge[0]);\n        }\n        \n\t\t// Iterate over all node to get their ancestors\n        for(int i=0; i<n; i++) {\n            vector<bool> vis(n, false);\n            dfs(adj, res, vis, i, i);\n        }\n        \n\t\t// In the end, sort list of ancestors of each node\n        for(int i=0; i<n; i++) {\n            sort(begin(res[i]), end(res[i]));\n        }\n        return res;\n    }\n};\n```\n\n**Complexity :**\n\n* Time : `O(N * N + N * (k log k))` , \n\t* N -> number of nodes\n\t* k -> average number of ancestors of each node \n\n* Space : `~ O(N * N)`\n\n-------------------------------\n\nNote : We can optimize this certainly by skipping sorting step. And store ancestors of each node in such a way that it remains in sorted order.\n\n------------------------------------\n\n**Optimization :**\n\n* Idea here is to build adjacency list such that we connect **parent -> child**.\n\n* Then iterate over all nodes, considering it as a **parent node**, and perform DFS.\n* Now, in DFS call, we pass **parent node**, and it would also be ancestor of all its adjacent nodes.\n\t* that we can reach from **parent node.**\n* In this way we can get ancestors in sorted order, since we start from 0 to n.\n\n# Code : \n\n```\nclass Solution {\nprivate:\n\tvoid dfs(vector<vector<int>>& adj, vector<vector<int>>& res, vector<bool>& vis, int node, int parent) {\n        vis[node] = true;\n\t\n        for(auto& adjnode : adj[node]) {\n            if(!vis[adjnode]) {\n                res[adjnode].push_back(parent);\n                dfs(adj, res, vis, adjnode, parent);\n            }\n        }\n    }\n\t\npublic:\n    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        \n        vector<vector<int>> adj(n); // adjacency list\n        vector<vector<int>> res(n); // List to store all ancestors of each node\n        \n        for(auto& edge : edges) {\n            adj[edge[0]].push_back(edge[1]);\n        }\n        \n        for(int i=0; i<n; i++) {\n            vector<bool> vis(n, false);\n            dfs(adj, res, vis, i, i);\n        }      \n\t\treturn res;\n    }\n};\n```\n\n**Complexity :**\n\n* Time : `O(N * N)` , \n\t* N -> number of nodes\n\n* Space : `~ O(N * N)`\n\n\n***If you find this helpful, do give it a like :)***
['Depth-First Search', 'Graph', 'C']