[LC]2192. 有向无环图中一个节点的所有祖先

🚩传送门：力扣题目

题目

给你一个正整数 ，它表示一个 有向无环图 中节点的数目，节点编号为 到 （包括两者）。

给你一个二维整数数组 ，其中 表示图中一条从 到 的单向边。

请你返回一个数组 ，其中是第 个节点的 所有祖先 ，这些祖先节点 升序 排序。

如果 通过一系列边，能够到达 ，那么我们称节点 是节点 的 祖先 节点。

示例 1：

输入：n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]] 输出：[[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]] 解释： 上图为输入所对应的图。

• 节点 0 ，1 和 2 没有任何祖先。
• 节点 3 有 2 个祖先 0 和 1 。
• 节点 4 有 2 个祖先 0 和 2 。
• 节点 5 有 3 个祖先 0 ，1 和 3 。
• 节点 6 有 5 个祖先 0 ，1 ，2 ，3 和 4 。
• 节点 7 有 4 个祖先 0 ，1 ，2 和 3 。

解题思路：拓扑排序

广度搜索

• 数组：记录所有结点 的入度，结点 入度为时需要入队
• 数组：记录所有结点 的直系父亲结点
• 数组：记录所有结点 的直系孩子结点

从队列中取出每一个入度为的结点 ，注意此时结点 的直系父亲结点 一定已经遍历完成，且计算结果保存在数组中，所以只要在数组中取出结点 的每一个直系父亲结点 ，将加入结果集，并将（代表 的所有祖先）的结果也加入到。

最后对 进行去重、排序 。插入中即可，有点麻烦处理，需要先删除处的空数组，在将插入。

我的代码

class Solution {
    public static List<List<Integer>> getAncestors(int n, int[][] edges) {
        int[]inedges=new int[n];                        // 入度数组
        List<List<Integer>>v_u_edges=new ArrayList<>(); // 记录所有v的直系父亲结点u
        List<List<Integer>>u_v_edges=new ArrayList<>(); // 记录所以u的直系孩子结点v
        List<List<Integer>>res=new ArrayList<>();
        // 为数组分配空间
        for (int i = 0; i < n; i++) {
            res.add(new ArrayList<>());
            v_u_edges.add(new ArrayList<>());
            u_v_edges.add(new ArrayList<>());
        }
        // 遍历 edges 记录所有v的入度,v 的直系父亲结点 u,u的直系孩子结点
        for (int i = 0; i < edges.length; i++) {
            inedges[edges[i][1]]++;
            u_v_edges.get(edges[i][0]).add(edges[i][1]);// 记录u的孩子v
            v_u_edges.get(edges[i][1]).add(edges[i][0]);// 记录v的父亲u
        }
        // 将入度为0的入队
        LinkedList<Integer>queue=new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inedges[i]==0) {
                queue.addLast(i);
            }
        }
        while(!queue.isEmpty()){
            int v=queue.pollFirst();
            // 添加 v 父亲
            HashSet<Integer>set=new HashSet<>();
            for(int u:v_u_edges.get(v)){
                set.add(u);    // 直系父亲
                // 父亲u的已经计算完成在 res 中的结果集拿过来
                for (int uu :res.get(u)) {
                    set.add(uu);
                }
            }
            // 去重
            List<Integer>temp=new ArrayList<>();
            for (Integer u:set){
                temp.add(u);
            }
            // 排序
            temp.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1-o2;
                }
            });
            // 先删除再插入
            res.remove(v);
            res.add(v,temp);
            // 此时 v 遍历完成,还需要将 v 的所有孩子的入度-1,当入度为0时入队
            for(int vv:u_v_edges.get(v)){
                inedges[vv]--;
                if(inedges[vv]==0)queue.addLast(vv);
            }
        }
        return res;
    }
}