'Intuition behind starting from the leaves instead of the parents
I am trying to solve this question from the contest earlier today:
You have a DAG with nodes from
0ton-1andedgeswhereedges[i] = [from_i, to_i]denotes that there is a unidirectional edge fromfrom_itoto_iin the graph. Return a listanswer, whereanswer[i]is the list of ancestors of theith node, sorted in ascending order.
Input: n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
Output: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
I initially construct the "graph" using adjacency list representation and then calculate the indegree of each node. I do a DFS with nodes with indegree 0 (since they are the oldest ancestors), i.e., nodes 0, 1 and 2 in above graph. Finally, I return the result:
class Solution {
public:
unordered_map<int, unordered_set<int>> graph;
unordered_map<int, set<int>> res;
vector<int> degrees;
void buildGraph(vector<vector<int>>& edges) {
for(auto& e: edges) {
graph[e[0]].insert(e[1]);
}
}
void indegrees() {
for(auto& s: graph) {
for(auto e: s.second) degrees[e]++;
}
}
void dfs(int i, vector<int>& ancestors) {
auto neighbors=graph[i];
for(auto& an: ancestors) res[i].insert(an);
if(neighbors.empty()) {
return;
}
ancestors.push_back(i);
for(auto& n: neighbors) {
dfs(n, ancestors);
}
ancestors.pop_back();
}
vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
buildGraph(edges);
degrees.resize(n,0);
indegrees();
// cout<<"\ndegrees:\n";
// for(auto each: degrees) cout<<each<<" ";
// cout<<"\n";
for(int i=0; i<degrees.size(); i++) {
if(!degrees[i]) {
vector<int> ancestors;
dfs(i, ancestors);
}
}
vector<vector<int>> ans(n);
for(int i=0; i<n; i++) {
vector<int> v;
if(!res.count(i)) {
ans[i]=v;
continue;
}
set<int>& st=res[i];
for(auto& each: st) v.push_back(each);
ans[i]=v;
}
return ans;
}
};
This works, but times out on large inputs such as this. However, code that starts from the children ("leaves") and traverse upwards towards the ancestors gets accepted.
My question is, is there some flaw in my logic (of starting with the ancestors) which makes it slow, or is the OJ missing some test cases for the latter scenario (of starting with the leaves)?
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|

