Formatted question description: https://leetcode.ca/all/2192.html

2192. All Ancestors of a Node in a Directed Acyclic Graph (Medium)

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.

 

Example 1:

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]]
Explanation:
The above diagram represents the input graph.
- Nodes 0, 1, and 2 do not have any ancestors.
- Node 3 has two ancestors 0 and 1.
- Node 4 has two ancestors 0 and 2.
- Node 5 has three ancestors 0, 1, and 3.
- Node 6 has five ancestors 0, 1, 2, 3, and 4.
- Node 7 has four ancestors 0, 1, 2, and 3.

Example 2:

Input: n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Output: [[],[0],[0,1],[0,1,2],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Node 0 does not have any ancestor.
- Node 1 has one ancestor 0.
- Node 2 has two ancestors 0 and 1.
- Node 3 has three ancestors 0, 1, and 2.
- Node 4 has four ancestors 0, 1, 2, and 3.

 

Constraints:

  • 1 <= n <= 1000
  • 0 <= edges.length <= min(2000, n * (n - 1) / 2)
  • edges[i].length == 2
  • 0 <= fromi, toi <= n - 1
  • fromi != toi
  • There are no duplicate edges.
  • The graph is directed and acyclic.

Companies:
Oracle, Google

Related Topics:
Depth-First Search, Breadth-First Search, Graph, Topological Sort

Similar Questions:

Solution 1. DFS

// OJ: https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& E) {
        vector<vector<int>> G(n), ans(n);
        bool connect[1001][1001] = {};
        for (auto &e : E) G[e[0]].push_back(e[1]);
        function<void(int, int)> dfs = [&](int u, int s) {
            if (connect[s][u]) return; // If `s` has been added as a source node of `u` already, skip
            connect[s][u] = true;
            for (int v : G[u]) dfs(v, s);
        };
        for (int i = 0; i < n; ++i) dfs(i, i);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i != j && connect[i][j]) ans[j].push_back(i);
            }
        }
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/
// Time: O(N^2)
// Space: O(E)
class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& E) {
        vector<vector<int>> G(n), ans(n);
        for (auto &e : E) G[e[0]].push_back(e[1]);
        function<void(int, int)> dfs = [&](int u, int s) {
            for (int v : G[u]) {
                if (ans[v].size() && ans[v].back() == s) continue;
                ans[v].push_back(s);
                dfs(v, s);
            }
        };
        for (int i = 0; i < n; ++i) dfs(i, i);
        return ans;
    }
};

All Problems

All Solutions