README_EN.md

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

中文文档

Description

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.

Solutions

BFS.

Python3

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        g = defaultdict(list)
        for u, v in edges:
            g[v].append(u)
        ans = []
        for i in range(n):
            if not g[i]:
                ans.append([])
                continue
            q = deque([i])
            vis = [False] * n
            vis[i] = True
            t = []
            while q:
                for _ in range(len(q)):
                    v = q.popleft()
                    for u in g[v]:
                        if not vis[u]:
                            vis[u] = True
                            q.append(u)
                            t.append(u)
            ans.append(sorted(t))
        return ans

Java

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; ++i) {
            g[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            g[e[1]].add(e[0]);
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            List<Integer> t = new ArrayList<>();
            if (g[i].isEmpty()) {
                ans.add(t);
                continue;
            }
            Deque<Integer> q = new ArrayDeque<>();
            q.offer(i);
            boolean[] vis = new boolean[n];
            vis[i] = true;
            while (!q.isEmpty()) {
                for (int j = q.size(); j > 0; --j) {
                    int v = q.poll();
                    for (int u : g[v]) {
                        if (!vis[u]) {
                            vis[u] = true;
                            q.offer(u);
                            t.add(u);
                        }
                    }
                }
            }
            Collections.sort(t);
            ans.add(t);
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        for (auto& e : edges) g[e[1]].push_back(e[0]);
        vector<vector<int>> ans;
        for (int i = 0; i < n; ++i) {
            vector<int> t;
            if (g[i].empty()) {
                ans.push_back(t);
                continue;
            }
            queue<int> q {{i}};
            vector<bool> vis(n);
            vis[i] = true;
            while (!q.empty()) {
                for (int j = q.size(); j > 0; --j) {
                    int v = q.front();
                    q.pop();
                    for (int u : g[v]) {
                        if (vis[u]) continue;
                        vis[u] = true;
                        q.push(u);
                        t.push_back(u);
                    }
                }
            }
            sort(t.begin(), t.end());
            ans.push_back(t);
        }
        return ans;
    }
};

Go

func getAncestors(n int, edges [][]int) [][]int {
	g := make([][]int, n)
	for _, e := range edges {
		g[e[1]] = append(g[e[1]], e[0])
	}
	var ans [][]int
	for i := 0; i < n; i++ {
		var t []int
		if len(g[i]) == 0 {
			ans = append(ans, t)
			continue
		}
		q := []int{i}
		vis := make([]bool, n)
		vis[i] = true
		for len(q) > 0 {
			for j := len(q); j > 0; j-- {
				v := q[0]
				q = q[1:]
				for _, u := range g[v] {
					if !vis[u] {
						vis[u] = true
						q = append(q, u)
						t = append(t, u)
					}
				}
			}
		}
		sort.Ints(t)
		ans = append(ans, t)
	}
	return ans
}

TypeScript

...