C++ Solution | Plain DFS | Short and Clean code
Simple DFS\nIdea is simple if you start from any node then the node that you will be visiting will have start node as an ancestor.\nLet us understand with an ex
Simple DFS\nIdea is simple if you start from any node then the node that you will be visiting will have start node as an ancestor.\nLet us understand with an example.\nLet\'s say i start from node 0 and i have visited node 1 node 3 and node 4 \nso node 0 will be ancestor of all node 1,3 and 4\n\n* Ancestor Meaning: " A node u is an ancestor of another node v if u can reach v via a set of edges"\n\n* Node 0 is ancestor of which all nodes?\n=> Start a DFS(/BFS) from node 0 as src, and all the reachable nodes will\nalways have node 0 as an ancestor [from definition]\n\n* Node 1 is ancestor of which all nodes?\n=> Start a DFS(/BFS) from node 1 as src, and all the reachable nodes will\nalways have node 1 as an ancestor [from definition of ancestor]\n\n* Node 2 is .....?\n=> Start a DFS(/BFS) from node 2, ....\n\n...\n\n* Node n is ancestor of which all nodes?\n=> Start a DFS(/BFS) from node n as src , and all the reachable nodes will\nalways have node n as an ancestor [from definition of ancestor]\n\n* Hence, you see that we will automatically have all the ancestors in\nincreasing order.\n\n* TC:O(N*N) Since for each src node (i) we do a DFS(/BFS) of entire graph form (i) and check which nodes are reachable\n\n* SC:O(N) for DFS(/BFS) + O(N^N) for returning answer\n\nThank you @[tbne1905](https://leetcode.com/tbne1905/) for such a nice explanation.\n\n```\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        \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```\n\nNow the `vis` array that we are using is an overhead to our code. So lets try to remove this.\nYou wonder how we will remove it? right?\nLets understand What\'s happening .\nIf we will not use `vis` array then the element for which we arleady added `starting node` as an ancestor we will be adding again and again if we keep visiting that node from some other path. Lets understand this with example.\nif we start from 0 and visited 2 ,3 ,4.\nso we have 0 as an ancestor for 2,3 and 4\nnow lets assume we have a directed edge from 3 to 2 \nso when we will go deeper in dfs then we will again visit 2 and we will put 0 as an ancestor of 2 again so we will be end up getting `[0,0]` so by using `vis` array we are removing this only so this can be removed by simple if logic\n\n```\nclass Solution {\npublic:\n    void dfs(vector<vector<int>> &graph,int i,int j,vector<vector<int>> &ans){\n        for(auto &x:graph[j]){\n            if(ans[x].empty() || ans[x].back()!=i){\n                ans[x].push_back(i);\n                dfs(graph,i,x,ans);\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            dfs(graph,i,i,ans);\n        }\n        return ans;\n    }\n};\n```\n\n**If you have any doubt ask in comment section ..I\'ll be happy to help**
['Depth-First Search', 'Graph', 'C', 'C++']