题目

有 n 个项目，每个项目或者不属于任何小组，或者属于 m 个小组之一。group[i] 表示第 i 个项目所属的小组，如果第 i 个项目不属于任何小组，则 group[i] 等于 -1。项目和小组都是从零开始编号的。可能存在小组不负责任何项目，即没有任何项目属于这个小组。

请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：

• 同一小组的项目，排序后在列表中彼此相邻。
• 项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。

如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表 。

示例 1：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
输出：[6,3,4,1,5,2,0,7]

示例 2：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
输出：[]
解释：与示例 1 大致相同，但是在排序后的列表中，4 必须放在 6 的前面。

提示：

• 1 <= m <= n <= 3 * 10⁴
• group.length == beforeItems.length == n
• -1 <= group[i] <= m - 1
• 0 <= beforeItems[i].length <= n - 1
• 0 <= beforeItems[i][j] <= n - 1
• i != beforeItems[i][j]
• beforeItems[i] 不含重复元素

思路

存储每个节点的入度，包括小组和项目的

解法

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        int[] inDegree = new int[n + m];//存储每个节点的入度，包括小组和项目的
        List<Integer>[] neis = new List[n + m];//存储下一个节点列表
        for (int i = 0; i < neis.length; i++) {
            neis[i] = new ArrayList<>();
        }
        for (int i = 0; i < group.length; i++) {
            if (group[i] != -1) {
                neis[group[i] + n].add(i);//将小组指向项目
                inDegree[i]++;//项目的入度加1
            }
        }
        for (int i = 0; i < beforeItems.size(); i++) {//当前项目
            List<Integer> befores = beforeItems.get(i);
            for (int b : befores) {//遍历前置的项目
                int curNode = (group[i] == -1 ? i : n + group[i]);//当前项目属于小组，则设置当前节点为小组节点，需要保证小组都完成
                int beforeNode = (group[b] == -1 ? b : n + group[b]);//前置项目属于小组，则设置前置节点为小组节点，需要保证小组都完成
                if (beforeNode == curNode) {//同小组内
                    neis[b].add(i);//绑定项目
                    inDegree[i]++;
                } else {
                    neis[beforeNode].add(curNode);
                    inDegree[curNode]++;
                }
            }
        }
        for (int i = 0; i < n + m; i++) {
            if (inDegree[i] == 0) {
                dfs(n, i, neis, inDegree);
            }
        }
        return (ans.size() == n) ? ans.stream().mapToInt(x -> x).toArray(): new int[]{};
    }

    List<Integer> ans = new ArrayList<>();

    public void dfs(int n, int cur, List<Integer>[] neis, int[] inDegree) {
        if (cur < n) {
            ans.add(cur);
        }
        inDegree[cur] = -1;//标记访问
        for (int nei : neis[cur]) {
            if (--inDegree[nei] == 0) {
                dfs(n, nei, neis, inDegree);
            }
        }
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现