※ 引述《smart0eddie (smart0eddie)》之铭言：
: 2024-06-29
: 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.
: 要记录每个 node 的所有 ancestor
: 也就是所有可以经过 edge 直接或间接走到这个 node 的 node
: 没意外就是 DFS 走
: 原本想要一条路径一路走下去的时候顺便把所有经过的 ancestor 一起带下去
: 走到底要往回的时候一次塞进去
: 但是因为是 DAG 一个 node 前面可能很多个 node 可以走到
: 而且没有一个独一的 root
: 要分辨有没有走过这条路有点麻烦
: 而且不同的路走到同一个 node 还是要往下走
: 所以选择我就抄.jpg
: 照 answer 一个一个 node 当 root 往下走 一次只推一个
: class Solution {
: public:
: vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
: vector<vector<int>> ancestors(n);
: vector<vector<int>> adjacent(n);
: // construct (sparse) adjacent map
: for (const auto& e : edges) {
: adjacent[e[0]].push_back(e[1]);
: }
: // traverse
: for (int i = 0; i < n; ++i) {
: vector<bool> visit(n, false);
: dfs(adjacent, i, i, ancestors, visit);
: }
: for (int i = 0; i < n; ++i) {
: sort(ancestors[i].begin(), ancestors[i].end());
: }
: return ancestors;
: }
: private:
: void dfs(vector<vector<int>>& adjacent, int root, int cur,
: vector<vector<int>>& ancestors, vector<bool>& visit) {
: visit[cur] = true;
: for (int next : adjacent[cur]) {
: if (!visit[next]) {
: ancestors[next].push_back(root);
: dfs(adjacent, root, next, ancestors, visit);
: }
: }
: }
: };
思路:
我本来想说纪录所有子节点的父节点
就record = {}
record[kid].append(ancestor)
然后再把父节点的父节点加上去
后来发现会重复 所以改用set()纪录
但改用set()又有排序问题
果断看解答 姆咪
Python Code:
class Solution:
def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
def dfs(ancestor,kid):
if not (result[kid] and result[kid][-1] == ancestor):
if kid != ancestor:
result[kid].append(ancestor)
for grand_child in record[kid]:
dfs(ancestor,grand_child)
record = defaultdict(list)
for edge in edges:
record[edge[0]].append(edge[1])
result = [[] for _ in range(n)]
for i in range(n):
dfs(i,i)
return result