Leetcode 2192 - All Ancestors of a Node in a Directed Acyclic Graph [29/6/24]
Вставка
- Опубліковано 27 чер 2024
- Time Taken: ~45 mins
Tag: LeetCode Medium
Basic ideas:
- Observation: By reversing all edges of graph, we can find all ancestors from a node by doing dfs or bfs from that node. Whichever node that can be reached would have been the ancestor of the node, for the original graph.
High-level Steps:
1. Reverse edges of graph
2. Traverse through reversed graph and do dfs/bfs for each node. Add unique nodes that can be reached from the traversal to the answer vector for that node.
3. Sort each vector in ans vector.