1203. Sort Items by Groups Respecting Dependencies ================================================== 题目信息 -------- :题号: 1203 :难度: Hard :主题: 拓扑排序、分组依赖、图 :原题: `LeetCode 1203 `_ :重点: 每个物品必须位于所有前置物品之后,同时同组物品在结果中必须连续;未分组物品可视为各自独立的新组 题目重述 -------- 有 ``n`` 个物品,编号为 ``0`` 到 ``n - 1``,以及 ``m`` 个已有分组。``group[i]`` 表示物品 ``i`` 所属组;值为 ``-1`` 的物品尚未分组。``beforeItems[i]`` 列出必须排在物品 ``i`` 之前的物品。 请返回包含全部物品的一种排列,使每项依赖都得到满足,并且属于同一组的所有物品在排列中形成一个连续区间。可以为每个未分组物品分配独立的新组。若不存在合法排列,返回空数组;若答案不唯一,可返回任意一种。 ``1 <= m <= n <= 3 * 10^4``,``group.length == beforeItems.length == n``;``group[i]`` 为 ``-1`` 或已有组编号,依赖下标均合法。 自建示例 -------- 跨组依赖与组内依赖可以同时满足: .. code-block:: text 输入:n = 4, m = 2, group = [0,0,1,1], beforeItems = [[],[0],[1],[2]] 输出:[0,1,2,3] 解释:0 必须先于 1,1 先于 2,2 先于 3;两个组也分别保持连续。 依赖形成环时没有合法顺序: .. code-block:: text 输入:n = 3, m = 1, group = [0,0,0], beforeItems = [[2],[0],[1]] 输出:[] 解释:依赖要求 2 在 0 前、0 在 1 前、1 又在 2 前,形成有向环。