2192. All Ancestors of a Node in a Directed Acyclic Graph
Approach
DFS/BFS from each node; collect ancestors in sorted order with deduplication.
Key Techniques
DFS explores as far as possible before backtracking. Use it for path finding, cycle detection, connected components, and tree traversal. Implement recursively (implicit call stack) or iteratively with an explicit Stack<T>. Mark visited nodes to avoid infinite loops in graphs.
BFS explores nodes level by level, guaranteeing the shortest path in unweighted graphs. Use a Queue<T> and a visited set. Classic applications: shortest path, level-order tree traversal, multi-source distance (e.g., "01 matrix"), and word ladder transformations.
Graph algorithms model relationships between entities. Core algorithms: DFS/BFS for traversal, Dijkstra for weighted shortest path, Bellman-Ford for negative weights, Floyd-Warshall for all-pairs, and Kruskal/Prim for minimum spanning trees. Represent graphs as adjacency lists (Dictionary<int, List<int>>) for efficiency.
// Approach: DFS/BFS from each node; collect ancestors in sorted order with deduplication.
// Time: O(n²) Space: O(n²)
public class Solution
{
public IList<IList<int>> GetAncestors(int n, int[][] edges)
{
var ans = new List<IList<int>>();
var adjList = new List<List<int>>();
for (int i = 0; i < n; i++)
{
ans.Add(new List<int>());
adjList.Add(new List<int>());
}
foreach (int[] edge in edges)
{
int u = edge[0];
int v = edge[1];
adjList[u].Add(v);
}
for (int i = 0; i < n; i++)
dfs(adjList, i, i, new bool[n], ans);
return ans;
}
private void dfs(List<List<int>> adjList, int node, int ancestor, bool[] seen, List<IList<int>> ans)
{
seen[node] = true;
foreach (int adjNode in adjList[node])
{
if (seen[adjNode])
continue;
ans[adjNode].Add(ancestor);
dfs(adjList, adjNode, ancestor, seen, ans);
}
}
}