All Ancestors of a Node in a Directed Acyclic Graph

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;
    }
};

class Solution {

    public List<List<Integer>> findAllAncestors(int vertices, int[][] relationships) {
        // Initialize adjacency list
        List<Integer>[] graph = new ArrayList[vertices];
        for (int vertex = 0; vertex < vertices; vertex++) {
            graph[vertex] = new ArrayList<>();
        }

        // Populate the graph and count in-degrees
        int[] inDegrees = new int[vertices];
        for (int[] relation : relationships) {
            int start = relation[0];
            int end = relation[1];
            graph[start].add(end);
            inDegrees[end]++;
        }

        // Queue for processing independent nodes (zero in-degree)
        Queue<Integer> zeroDegreeNodes = new LinkedList<>();
        for (int i = 0; i < vertices; i++) {
            if (inDegrees[i] == 0) {
                zeroDegreeNodes.add(i);
            }
        }

        // Sorting nodes topologically
        List<Integer> sortedNodes = new ArrayList<>();
        while (!zeroDegreeNodes.isEmpty()) {
            int current = zeroDegreeNodes.poll();
            sortedNodes.add(current);
            for (int adjNode : graph[current]) {
                inDegrees[adjNode]--;
                if (inDegrees[adjNode] == 0) {
                    zeroDegreeNodes.add(adjNode);
                }
            }
        }

        // Sets to store ancestors and result list initiation
        List<List<Integer>> ancestors = new ArrayList<>();
        List<Set<Integer>> ancestorSets = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            ancestors.add(new ArrayList<>());
            ancestorSets.add(new HashSet<>());
        }

        // Determine each node's ancestors
        for (int node : sortedNodes) {
            for (int adjacent : graph[node]) {
                ancestorSets.get(adjacent).add(node);
                ancestorSets.get(adjacent).addAll(ancestorSets.get(node));
            }
        }

        // Converting set to list for the final output
        for (int i = 0; i < vertices; i++) {
            for (int ancestor : ancestorSets.get(i)) {
                ancestors.get(i).add(ancestor);
            }
        }

        return ancestors;
    }
}

class Solution:
    def ancestorFinder(self, total_nodes, connections):
        # Adjacency representation of the graph
        adjacency_structure = [[] for _ in range(total_nodes)]

        # Creating initial node dependencies
        node_indegree = [0] * total_nodes
        for src, dest in connections:
            adjacency_structure[src].append(dest)
            node_indegree[dest] += 1

        # Nodes with no prerequisites
        entry_points = [node for node in range(total_nodes) if node_indegree[node] == 0]

        # Result of nodes in dependency order
        dependency_order = []
        while entry_points:
            active_node = entry_points.pop(0)
            dependency_order.append(active_node)

            # Updating indegrees and managing new possible entry points
            for linked_node in adjacency_structure[active_node]:
                node_indegree[linked_node] -= 1
                if node_indegree[linked_node] == 0:
                    entry_points.append(linked_node)

        # Preparing the ancestor list output
        result_ancestors = [[] for _ in range(total_nodes)]
        ancestor_tracker = [set() for _ in range(total_nodes)]

        # Building the ancestor relationships from ordered nodes
        for processed_node in dependency_order:
            for connected_node in adjacency_structure[processed_node]:
                ancestor_tracker[connected_node].add(processed_node)
                ancestor_tracker[connected_node].update(ancestor_tracker[processed_node])

        # Converting ancestor sets to sorted lists
        for index, ancestors in enumerate(ancestor_tracker):
            result_ancestors[index] = sorted(ancestors)

        return result_ancestors