2192. All Ancestors of a Node in a Directed Acyclic Graph

You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive).

You are also given a 2D integer array edges, where edges[i] = [fromi, toi] denotes that there is a unidirectional edge from fromi to toi in the graph.

Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order.

A node u is an ancestor of another node v if u can reach v via a set of edges.

class Solution {
    vector<vector<int>> g;
    vector<int> count;
    vector<unordered_set<int>> parent;
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> res(n);
        g = vector<vector<int>>(n);
        count = vector<int>(n);
        parent = vector<unordered_set<int>>(n);
        
        for(auto e : edges) {
            g[e[0]].push_back(e[1]);
            count[e[1]]++;
        }
        queue<int> q;
        for(int i = 0; i < n; i++) {
            if(count[i] == 0) {
                q.push(i);
            }
        }
        
        while(!q.empty()) {
            auto node = q.front(); q.pop();
            res[node] = vector<int>(parent[node].begin(), parent[node].end());
            sort(res[node].begin(), res[node].end());
            
            for(auto child : g[node]) {
                parent[child].insert(node);
                parent[child].insert(parent[node].begin(), parent[node].end());
                if(--count[child] == 0) {
                    q.push(child);
                }
            }
        }
        return res;
    }
};