'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 0 to n-1 and edges where edges[i] = [from_i, to_i] denotes that there is a unidirectional edge from from_i to to_i in the graph. Return a list answer, where answer[i] is the list of ancestors of the ith 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]]

Graph

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