"Finding All Ancestors in a Directed Acyclic Graph (DAG)"-Java Solution
Intuition :-\n- To find all ancestors of each node in a Directed Acyclic Graph (DAG), you can leverage topological sorting and breadth-first search (BFS) to pro
# Intuition :-\n- To find all ancestors of each node in a Directed Acyclic Graph (DAG), you can leverage topological sorting and breadth-first search (BFS) to propagate ancestor information through the graph.\n\n# Approach :-\n1. Graph Representation: Create an adjacency list for the graph and an array to store the in-degree of each node.\n1. Topological Sorting: Use BFS to process nodes in topological order, starting with nodes having zero in-degree.\n1. Track Ancestors: Maintain a matrix to record ancestor relationships as you traverse the graph.\n1. Build Result: Convert the matrix into a list of lists, where each list contains the ancestors of the corresponding node.\n\n# Complexity\n- Time complexity :- O(n^2), as each node and edge is processed, and ancestor propagation takes \uD835\uDC42(\uD835\uDC5B2) in the worst case.\n\n- Space complexity:- O(n^2), for storing the ancestor matrix and adjacency list.\n\n# Code\n```\nclass Solution {\n    public List<List<Integer>> getAncestors(int n, int[][] edges) {\n        List<List<Integer>> graph = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            graph.add(new ArrayList<>());\n        }\n        int indegree[] = new int[n];\n        for (int edge[] : edges) {\n            indegree[edge[1]]++;\n            graph.get(edge[0]).add(edge[1]);\n        }\n        Queue<Integer> q = new LinkedList<>();\n        for (int i = 0; i < n; i++) {\n            if (indegree[i] == 0)\n                q.add(i);\n        }\n        int[][] ancestor = new int[n][n];\n        while (!q.isEmpty()) {\n            int curr = q.poll();\n            for (int nei : graph.get(curr)) {\n                for (int i = 0; i < n; i++) {\n                    if (ancestor[curr][i] == 1 || i == curr) {\n                        ancestor[nei][i] = 1;\n                    }\n                }\n                if (--indegree[nei] == 0)\n                    q.add(nei);\n            }\n        }\n        List<List<Integer>> res = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            List<Integer> sub = new ArrayList<>();\n            for (int j = 0; j < n; j++) {\n                if (ancestor[i][j] == 1)\n                    sub.add(j);\n            }\n            res.add(sub);\n        }\n        return res;\n    }\n}\n```\n**Conclusion**\n- The solution efficiently determines all ancestors of each node in a Directed Acyclic Graph (DAG) using topological sorting and breadth-first search (BFS). By propagating ancestor information during the BFS traversal, it builds a comprehensive ancestor matrix. This matrix is then transformed into the required list format, providing a clear and structured representation of each node\'s ancestors. The approach ensures that the solution is both time and space efficient, making it suitable for handling large graphs within reasonable constraints.
['Java']