README.md

2192. 有向无环图中一个节点的所有祖先

English Version

题目描述

给你一个正整数 n ，它表示一个 有向无环图 中节点的数目，节点编号为 0 到 n - 1 （包括两者）。

给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。

请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有 祖先 ，这些祖先节点 升序 排序。

如果 u 通过一系列边，能够到达 v ，那么我们称节点 u 是节点 v 的 祖先 节点。

 

示例 1：

输入：n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
输出：[[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
解释：
上图为输入所对应的图。
- 节点 0 ，1 和 2 没有任何祖先。
- 节点 3 有 2 个祖先 0 和 1 。
- 节点 4 有 2 个祖先 0 和 2 。
- 节点 5 有 3 个祖先 0 ，1 和 3 。
- 节点 6 有 5 个祖先 0 ，1 ，2 ，3 和 4 。
- 节点 7 有 4 个祖先 0 ，1 ，2 和 3 。

示例 2：

输入：n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
输出：[[],[0],[0,1],[0,1,2],[0,1,2,3]]
解释：
上图为输入所对应的图。
- 节点 0 没有任何祖先。
- 节点 1 有 1 个祖先 0 。
- 节点 2 有 2 个祖先 0 和 1 。
- 节点 3 有 3 个祖先 0 ，1 和 2 。
- 节点 4 有 4 个祖先 0 ，1 ，2 和 3 。

 

提示：

• 1 <= n <= 1000
• 0 <= edges.length <= min(2000, n * (n - 1) / 2)
• edges[i].length == 2
• 0 <= fromi, toi <= n - 1
• fromi != toi
• 图中不会有重边。
• 图是 有向 且 无环 的。

解法

方法一：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];
        Arrays.setAll(g, k -> 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

...