All Ancestors of a Node in a Directed Acyclic Graph

Problem Statement

In this task, you're given a Directed Acyclic Graph (DAG) constituted of n nodes, labeled from 0 to n-1. You are provided with the description of the DAG in the form of a 2D integer array edges, where each entry edges[i] = [fromi, toi] signifies a unidirectional edge stemming from node fromi leading to node toi.

Your objective is to determine and return a list answer, where for each node i in the DAG, answer[i] contains a sorted list of nodes that are ancestors of node i. In other words, a node u is considered an ancestor of another node v if there exists a directed trail of edges from u to v.

Examples

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.

Approach and Intuition

When solving this problem, think about the direct relationship between nodes in terms of ancestry where a node can influence another through a series of connections (edges). The plan involves:

1. Graph Representation: Representing the graph using adjacency lists helps in easily traversing from any given node.

2. Traversing the Graph: For determining the ancestors of each node, we can employ Depth-First Search (DFS) or Breadth-First Search (BFS). DFS is particularly useful in exploring the depths of each potential ancestral chain.

3. Ancestor Tracking: Using a recursive or iterative approach, you can backtrack from each node up to its ultimate predecessors (origin nodes with no incoming edges), thus marking the reachable ancestors.

4. Result Compilation: After assessing all possible routes from every node, compile the list of ancestors for each node into a final result list where each sublist contains the ancestors sorted in ascending order.

• Complexity Consideration: Given n nodes and the edges constraints, the computation needs careful consideration to remain efficient. The graph traversal typically would be in the order of O(V + E) where V is the number of vertices and E is the number of edges. However, discovering all ancestors might appear more complex due to repeated traversals; hence, optimizing with memoization or reducing redundant checks is beneficial.

• Examples Review: The examples provided in the problem play a critical role in demonstrating simple to complex relationships between nodes and how they extrapolate to ancestor lists. Visualization of the graph structure based on these examples can add clarity to the traversal and ancestor discovery strategies.

Solutions

class Solution {
public:
    vector<vector<int>> findAncestors(int totalNodes, vector<vector<int>>& relations) {
        // Build adjacency list representation of graph
        vector<vector<int>> adjList(totalNodes);
    
        // Initialize indegrees and build graph structure from relations
        vector<int> nodeInDegree(totalNodes, 0);
        for (auto& rel : relations) {
            int start = rel[0];
            int end = rel[1];
            adjList[start].push_back(end);
            nodeInDegree[end]++;
        }
    
        queue<int> zeroIndegreeNodes;
        for (int i = 0; i < nodeInDegree.size(); i++) {
            if (nodeInDegree[i] == 0) {
                zeroIndegreeNodes.push(i);
            }
        }
    
        // Prepare for topological sorting
        vector<int> topologicalSortResult;
        while (!zeroIndegreeNodes.empty()) {
            int node = zeroIndegreeNodes.front();
            zeroIndegreeNodes.pop();
            topologicalSortResult.push_back(node);
    
            // Adjust indegrees based on adjacency list
            for (int adjNode : adjList[node]) {
                nodeInDegree[adjNode]--;
                if (nodeInDegree[adjNode] == 0) {
                    zeroIndegreeNodes.push(adjNode);
                }
            }
        }
    
        // Ancestral tracking using a set for unique ancestors
        vector<vector<int>> ancestors(totalNodes);
        vector<unordered_set<int>> ancestorSets(totalNodes);
    
        // Process nodes in order determined by topological sort
        for (int node : topologicalSortResult) {
            for (int adjNode : adjList[node]) {
                ancestorSets[adjNode].insert(node);
                ancestorSets[adjNode].insert(
                    ancestorSets[node].begin(),
                    ancestorSets[node].end());
            }
        }
    
        // Convert ancestral sets into sorted lists
        for (int i = 0; i < ancestors.size(); i++) {
            ancestors[i].assign(ancestorSets[i].begin(), ancestorSets[i].end());
            sort(ancestors[i].begin(), ancestors[i].end());
        }
    
        return ancestors;
    }
};