【Day 31 】2023-03-16 - 1203. 项目管理

[azl397985856]

1203. 项目管理

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/sort-items-by-groups-respecting-dependencies/

前置知识

• 图论
• 拓扑排序
• BFS & DFS

  题目描述

公司共有 n 个项目和  m 个小组，每个项目要不无人接手，要不就由 m 个小组之一负责。

group[i] 表示第 i 个项目所属的小组，如果这个项目目前无人接手，那么 group[i] 就等于 -1。（项目和小组都是从零开始编号的）小组可能存在没有接手任何项目的情况。

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

同一小组的项目，排序后在列表中彼此相邻。 项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。 如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表 。

 

示例 1：

![](https://p.ipic.vip/nrmqt5.jpg)

输入：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 * 104 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] 不含重复元素

[zol013]

class Solution:
    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:
            if indegree[item] == 0:
                q.append(item)

        while q:
            cur = q.popleft()
            ans.append(cur)
            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    q.append(neighbor)

        return ans

    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        max_group_id = m

        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = defaultdict(int)
        group_indegree = defaultdict(int)
        project_neighbors = defaultdict(list)
        group_neighbors = defaultdict(list)
        group_projects = defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for pre in beforeItems[project]:
                if group[pre] != group[project]:
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)

        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []
        ans = []

        for group_id in group_queue:
            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []

            ans += project_queue

        return ans

[JasonQiu]

• Assign each of the group-less items to a new group

• Run Topological Sort on groups and items, respectively

  class Solution:
  def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
      def topoSort(nodes: List[int], adj_matrix: List[List[int]], in_degree: List[int]):
          q = collections.deque()
          result = []
          for node in nodes:
              if in_degree[node] == 0:
                  q.append(node)
          while q:
              node = q.popleft()
              result.append(node)
              for next_node in adj_matrix[node]:
                  in_degree[next_node] -= 1
                  if in_degree[next_node] == 0:
                      q.append(next_node)
          return result if len(result) == len(nodes) else []
  
      for item_id, group_of_item in enumerate(group):
          if group_of_item == -1:
              group[item_id] = m
          m += 1
  
      adj_item = defaultdict(list)
      adj_group = defaultdict(list)
      indegree_item = [0] * n
      indegree_group = [0] * m
  
      for i in range(n):
          for before_item in beforeItems[i]:
              adj_item[before_item].append(i)
              indegree_item[i] += 1
      if (item_topo_sorted := topoSort(range(n), adj_item, indegree_item)) == []:
          return []
  
      for i, curr_group in enumerate(group):
          for before_item in beforeItems[i]:
              group_of_before_item = group[before_item]
              if curr_group != group_of_before_item:
                  adj_group[group_of_before_item].append(curr_group)
                  indegree_group[curr_group] += 1
      if (group_topo_sorted := topoSort(range(m), adj_group, indegree_group)) == []:
          return []
  
      item_by_group = defaultdict(list)
      for item in item_topo_sorted:
          item_by_group[group[item]].append(item)
      result = []
      for group in group_topo_sorted:
          result.extend(item_by_group[group])
      return result

  Time: O(v + e) Space: O(v + e)

[NorthSeacoder]

//先看懂....
/**
 * @param {number} n
 * @param {number} m
 * @param {number[]} group
 * @param {number[][]} beforeItems
 * @return {number[]}
 */
var sortItems = function(n, m, group, beforeItems) {
    // 思路，拓扑排序，建立组间依赖和组内依赖
    // 先排序组间依赖，之后再依照排序好的组间依赖，对每个组排序组内依赖
    let res = [];
    //组id的graph
    const groupGraph = new Map();
    //对应每个组的组内的graph
    const itemGraph = new Map();
    //每个group中的所有item
    const groupItemMap = new Map();
    //对于-1的组（不属于任何组），我们要对它们从m开始赋予不同的组，不然-1会被认为是同一个组
    let maxGroupNum = m;
    for (let i = 0; i < n; i++) {
        if (group[i] === -1) {
            group[i] = maxGroupNum;
            maxGroupNum++;
        }
    }
    // 建立groupItemMap
    for (let i = 0; i < n; i++) {
        if (!groupItemMap.has(group[i])) groupItemMap.set(group[i], []);
        groupItemMap.get(group[i]).push(i);
    }
    //建立依赖图
    for (let i = 0; i < beforeItems.length; i++) {
        let afterItemId = i;
        let beforeItemIds = beforeItems[i];
        for (let beforeItemId of beforeItemIds) {
            let beforeGroupId = group[beforeItemId],
                afterGroupId = group[afterItemId];
            if (beforeGroupId !== afterGroupId) {
                // 建立组间依赖
                if (!groupGraph.has(beforeGroupId)) groupGraph.set(beforeGroupId, []);
                groupGraph.get(beforeGroupId).push(afterGroupId);
            } else {
                // 建立组内依赖
                if (!itemGraph.has(beforeGroupId)) itemGraph.set(beforeGroupId, new Map());
                if (!itemGraph.get(beforeGroupId).has(beforeItemId)) itemGraph.get(beforeGroupId).set(beforeItemId, []);
                itemGraph
                    .get(beforeGroupId)
                    .get(beforeItemId)
                    .push(afterItemId);
            }
        }
    }
    // 1. 首先对组间依赖进行拓扑排序
    let groupDegrees = Array(maxGroupNum).fill(0);
    groupGraph.forEach((values) => values.forEach((value) => groupDegrees[value]++));
    let sortedGroupList = topoSort(groupDegrees, groupGraph, maxGroupNum);

    // 2. 再根据每个组进行组内的拓扑排序
    let items, itemDegrees, sortedItemList;
    for (let groupId of sortedGroupList) {
        if (!groupItemMap.has(groupId)) continue; // 注意题目，A group can have no item belonging to it
        items = groupItemMap.get(groupId);
        if (!itemGraph.has(groupId)) {
            // 这个group里的item没有依赖关系，则直接加入
            res = res.concat(items);
        } else {
            // 有组内依赖关系，则拓扑排序
            itemDegrees = Array(n).fill(-1);
            items.forEach((item) => (itemDegrees[item] = 0)); // 存在的item置为0
            itemGraph.get(groupId).forEach((values) => values.forEach((value) => itemDegrees[value]++));
            sortedItemList = topoSort(itemDegrees, itemGraph.get(groupId), items.length);
            if (sortedItemList.length === 0) return []; // 如果返回一个空数组，则说明不能完成拓扑排序，则是不可能的情况
            res = res.concat(sortedItemList);
        }
    }
    return res;
};
const topoSort = (degrees, graph, len) => {
    const res = [],
        q = [];
    for (let i = 0; i < degrees.length; i++) {
        if (degrees[i] === 0) q.push(i);
    }
    while (q.length !== 0) {
        let item = q.shift();
        res.push(item);
        if (graph.has(item)) {
            for (let child of graph.get(item)) {
                degrees[child]--;
                if (degrees[child] === 0) q.push(child);
            }
        }
    }
    return res.length === len ? res : []; // ans的长度不等于传入的长度，则说明不能完成拓扑排序，返回空数组
};

• TC:O(n+m)
• SC:O(n+m)

[RestlessBreeze]

code

class Solution {
public:
    vector<int> topSort(vector<int>& deg, vector<vector<int>>& graph, vector<int>& items) {
        queue<int> Q;
        for (auto& item: items) {
            if (deg[item] == 0) {
                Q.push(item);
            }
        }
        vector<int> res;
        while (!Q.empty()) {
            int u = Q.front(); 
            Q.pop();
            res.emplace_back(u);
            for (auto& v: graph[u]) {
                if (--deg[v] == 0) {
                    Q.push(v);
                }
            }
        }
        return res.size() == items.size() ? res : vector<int>{};
    }

    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<vector<int>> groupItem(n + m);
        vector<vector<int>> groupGraph(n + m);
        vector<vector<int>> itemGraph(n);

        vector<int> groupDegree(n + m, 0);
        vector<int> itemDegree(n, 0);

        vector<int> id;
        for (int i = 0; i < n + m; ++i) {
            id.emplace_back(i);
        }

        int leftId = m;

        for (int i = 0; i < n; ++i) {
            if (group[i] == -1) {
                group[i] = leftId;
                leftId += 1;
            }
            groupItem[group[i]].emplace_back(i);
        }

        for (int i = 0; i < n; ++i) {
            int curGroupId = group[i];
            for (auto& item: beforeItems[i]) {
                int beforeGroupId = group[item];
                if (beforeGroupId == curGroupId) {
                    itemDegree[i] += 1;
                    itemGraph[item].emplace_back(i);   
                } else {
                    groupDegree[curGroupId] += 1;
                    groupGraph[beforeGroupId].emplace_back(curGroupId);
                }
            }
        }

        vector<int> groupTopSort = topSort(groupDegree, groupGraph, id); 
        if (groupTopSort.size() == 0) {
            return vector<int>{};
        } 
        vector<int> ans;

        for (auto& curGroupId: groupTopSort) {
            int size = groupItem[curGroupId].size();
            if (size == 0) {
                continue;
            }
            vector<int> res = topSort(itemDegree, itemGraph, groupItem[curGroupId]);
            if (res.size() == 0) {
                return vector<int>{};
            }
            for (auto& item: res) {
                ans.emplace_back(item);
            }
        }
        return ans;
    }
};

[kofzhang]

思路

拓扑排序（不会做）

复杂度

挺高的

代码（抄的）

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        for i in range(n):
            if group[i] == -1:
                group[i] = m
                m = m + 1
        groupAdj, itemAdj = [[] for _ in range(m)], [[] for _ in range(n)]
        groupsIndegree, itemsIndegree = [0] * m, [0] * n
        for i in range(n):
            currentGroup = group[i]
            for item in beforeItems[i]:
                beforeGroup = group[item]
                if beforeGroup != currentGroup:
                    groupAdj[beforeGroup].append(currentGroup)
                    groupsIndegree[currentGroup] += 1

        for i in range(n):
            for item in beforeItems[i]:
                itemAdj[item].append(i)
                itemsIndegree[i] += 1

        groupsList = self.topologicalSort(groupAdj, groupsIndegree, m)
        if not groupsList: return []
        itemsList = self.topologicalSort(itemAdj, itemsIndegree, n)
        if not itemsList: return []

        groups2items = collections.defaultdict(list)
        for item in itemsList:
            groups2items[group[item]].append(item)

        ans = []
        for group in groupsList:
            ans.extend(groups2items[group])
        return ans

    def topologicalSort(self, adj, indegree, n):
        queue, res = [], []
        for i in range(n):
            if indegree[i] == 0:
                queue.append(i)

        while queue:
            node = queue.pop(0)
            res.append(node)
            for i in adj[node]:
                indegree[i] -= 1
                if indegree[i] == 0:
                    queue.append(i)
        return res if len(res) == n else None

[bookyue]

TC: O(n + m)
SC: O(n + m)

    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        for (int i = 0; i < group.length; i++) {
            if (group[i] == -1) group[i] = m++;
        }

        List<List<Integer>> groupAdj = new ArrayList<>(m);
        for (int i = 0; i < m; i++) groupAdj.add(new ArrayList<>());

        List<List<Integer>> itemAdj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) itemAdj.add(new ArrayList<>());

        int[] groupsIndegree = new int[m];
        int[] itemsIndegree = new int[n];

        for (int i = 0; i < group.length; i++) {
            int currentGroup = group[i];
            for (var beforeItem : beforeItems.get(i)) {
                int beforeGroup = group[beforeItem];
                if (beforeGroup == currentGroup) continue;
                groupAdj.get(beforeGroup).add(currentGroup);
                groupsIndegree[currentGroup]++;
            }
        }

        for (int i = 0; i < n; i++) {
            for (var beforeItem : beforeItems.get(i)) {
                itemAdj.get(beforeItem).add(i);
                itemsIndegree[i]++;
            }
        }

        List<Integer> groupList = topologicalSort(groupAdj, groupsIndegree, m);
        if (groupList.isEmpty()) return new int[0];

        List<Integer> itemList = topologicalSort(itemAdj, itemsIndegree, n);
        if (itemList.isEmpty()) return new int[0];

        Map<Integer, List<Integer>> groups2Items = new HashMap<>();
        for (int item : itemList)
            groups2Items.computeIfAbsent(group[item], i -> new ArrayList<>()).add(item);

        int idx = 0;
        int[] res = new int[n];
        for (int groupId : groupList) {
            if (!groups2Items.containsKey(groupId)) continue;
            for (int item : groups2Items.get(groupId))
                res[idx++] = item;
        }

        return res;
    }

    private List<Integer> topologicalSort(List<List<Integer>> graph, int[] indegree, int n) {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++)
            if (indegree[i] == 0) queue.offer(i);

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            res.add(cur);
            for (int successor : graph.get(cur)) {
                indegree[successor]--;
                if (indegree[successor] == 0)
                    queue.offer(successor);
            }
        }

        return res.size() == n ? res : List.of();
    }

[FlipN9]

/**
    topological sort: 

    [6(0), 3(0), 4(0), 1(-1), 5(1), 2(1), 0(-1), 7(-1)]
    -----------------  -----  ----------  ------------
    思路一: (这个比较巧妙)
    将 group 和 item 的关系存在一张 graph 中
        graph[N + groupId] 是 group
        graph[0 ... N + 1] 是 item
        * 对于不属于任何一组的 item, 其实没必要给它一个新组, 因为它可能会穿插在别的组之间

    对于 graph 的关系
        item 存在先后顺序, group 也存在先后顺序
        item --> group      indegree[group]++       根据 group 生成
        groupA --> groupB   indegree[groupB]++;     根据 beforeItems 生成

    思路二:
    先确定 group 的先后, 再确认 item 的先后

    TC: O(N + M)    SC: O(N + M)
*/
class Solution {
    int[] res;
    int idx;

    public int[] sortItems(int N, int M, int[] group, List<List<Integer>> beforeItems) {
        int[] indegree = new int[N + M];
        List<Integer>[] graph = new ArrayList[N + M];
        for (int i = 0; i < N + M; i++) graph[i] = new ArrayList<>();
        // 建立 group 的 关系
        for (int i = 0; i < N; i++) {
            if (group[i] == -1) continue;
            graph[N + group[i]].add(i);
            indegree[i]++;
        }
        // 在 group 的基础上, 把 item 放入 group 的列表中
        for (int i = 0; i < N; i++) {
            for (int before : beforeItems.get(i)) { // before --> item
                // find the groupID of i and beforeItem
                int a = group[before] == -1? before: N + group[before];
                int b = group[i] == -1? i : N + group[i];
                if (a == b) { // same group
                    graph[before].add(i);
                    indegree[i]++;
                } else {
                    graph[a].add(b);
                    indegree[b]++;
                }
            }
        }
        // topological sort
        res = new int[N]; idx = 0;
        for (int i = 0; i < N + M; i++) {
            if (indegree[i] == 0)
                dfs(N, graph, indegree, i);
        }
        return (idx == N) ? res : new int[]{};
    }

    private void dfs(int N, List<Integer>[] graph, int[] indegree, int cur) {
        if (cur < N) 
            res[idx++] = cur;
        indegree[cur]--; // 为了使每个 cur 只触动是否加入 res 一次, 到零之后减成-1
        for (int next : graph[cur]) {
            if (--indegree[next] == 0)
                dfs(N, graph, indegree, next);
        }
    }
}

[JiangyanLiNEU]

···python3 class Solution: def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]: for i in range(n): if group[i] == -1: group[i] = i + m # re-group

    graph0 = {} # digraph of groups 
    indeg0 = [0]*(m+n) # indegree of groups 

    graph1 = {} # digrpah of items 
    indeg1 = [0]*n # indegree of items

    for i, x in enumerate(beforeItems): 
        for xx in x: 
            if group[xx] != group[i]: 
                graph0.setdefault(group[xx], []).append(group[i])
                indeg0[group[i]] += 1
            graph1.setdefault(xx, []).append(i)
            indeg1[i] += 1

    def fn(graph, indeg): 
        """Return topological sort of graph using Kahn's algo."""
        ans = []
        stack = [k for k in range(len(indeg)) if indeg[k] == 0]
        while stack: 
            n = stack.pop()
            ans.append(n)
            for nn in graph.get(n, []):
                indeg[nn] -= 1
                if indeg[nn] == 0: stack.append(nn)
        return ans 

    tp0 = fn(graph0, indeg0) 
    if len(tp0) != len(indeg0): return [] 

    tp1 = fn(graph1, indeg1)
    if len(tp1) != len(indeg1): return []

    mp0 = {x: i for i, x in enumerate(tp0)}
    mp1 = {x: i for i, x in enumerate(tp1)}

    return sorted(range(n), key=lambda x: (mp0[group[x]], mp1[x]))

[duke-github]

思路

拓扑排序

复杂度

时间复杂度O(m+n*n)  空间复杂度O(m+n*n) 

代码

public class Solution {

    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // 第 1 步：数据预处理，给没有归属于一个组的项目编上组号
        for (int i = 0; i < group.length; i++) {
            if (group[i] == -1) {
                group[i] = m;
                m++;
            }
        }

        // 第 2 步：实例化组和项目的邻接表
        List<Integer>[] groupAdj = new ArrayList[m];
        List<Integer>[] itemAdj = new ArrayList[n];
        for (int i = 0; i < m; i++) {
            groupAdj[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            itemAdj[i] = new ArrayList<>();
        }

        // 第 3 步：建图和统计入度数组
        int[] groupsIndegree = new int[m];
        int[] itemsIndegree = new int[n];

        int len = group.length;
        for (int i = 0; i < len; i++) {
            int currentGroup = group[i];
            for (int beforeItem : beforeItems.get(i)) {
                int beforeGroup = group[beforeItem];
                if (beforeGroup != currentGroup) {
                    groupAdj[beforeGroup].add(currentGroup);
                    groupsIndegree[currentGroup]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (Integer item : beforeItems.get(i)) {
                itemAdj[item].add(i);
                itemsIndegree[i]++;
            }
        }

        // 第 4 步：得到组和项目的拓扑排序结果
        List<Integer> groupsList = topologicalSort(groupAdj, groupsIndegree, m);
        if (groupsList.size() == 0) {
            return new int[0];
        }
        List<Integer> itemsList = topologicalSort(itemAdj, itemsIndegree, n);
        if (itemsList.size() == 0) {
            return new int[0];
        }

        // 第 5 步：根据项目的拓扑排序结果，项目到组的多对一关系，建立组到项目的一对多关系
        // key：组，value：在同一组的项目列表
        Map<Integer, List<Integer>> groups2Items = new HashMap<>();
        for (Integer item : itemsList) {
            groups2Items.computeIfAbsent(group[item], key -> new ArrayList<>()).add(item);
        }

        // 第 6 步：把组的拓扑排序结果替换成为项目的拓扑排序结果
        List<Integer> res = new ArrayList<>();
        for (Integer groupId : groupsList) {
            List<Integer> items = groups2Items.getOrDefault(groupId, new ArrayList<>());
            res.addAll(items);
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    private List<Integer> topologicalSort(List<Integer>[] adj, int[] inDegree, int n) {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            Integer front = queue.poll();
            res.add(front);
            for (int successor : adj[front]) {
                inDegree[successor]--;
                if (inDegree[successor] == 0) {
                    queue.offer(successor);
                }
            }
        }

        if (res.size() == n) {
            return res;
        }
        return new ArrayList<>();
    }
}

[harperz24]

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
        max_group_id = m
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = collections.defaultdict(int)
        group_indegree = collections.defaultdict(int)
        project_neighbors = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        group_projects = collections.defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for pre in pres[project]:
                if group[pre] != group[project]:
                    # 小组关系图
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    # 项目关系图
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)

        ans = []
        # 先对组进行拓扑排序
        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []

        for group_id in group_queue:
            # 对小组中的项目进行拓扑排序
            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans += project_queue

        return ans

    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)

        return ans

[FireHaoSky]

思路：

"""
双拓扑排序，
1：修改分组信息
2：建立组内和组间的领接矩阵
3：拓扑排序，可以使用DFS，BFS
4：先进行组内排序，然后进行组间排序，如果没问题，合成答案
5：其实我也没看懂，看写完能不能懂
"""

代码：python

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        """
        n:项目数
        m:小组数
        group:项目所属
        beforeItems:项目前置任务，即简单拓扑要解决的排序问题
        """
        # 修改分组信息
        groupIndex2groupMember = defaultdict(list) # 保存了{小组：[项目]}
        for i in range(n):
            if group[i] == -1:
                group[i] = m
                m += 1
            groupIndex2groupMember[group[i]].append(i)

        # 2:组内和组间建领接矩阵
        inter = defaultdict(list)  # 组间
        inner = defaultdict(lambda:defaultdict(list))   # 组内
        for i in range(n):
            for j in beforeItems[i]:
                # j -> i
                if group[i] == group[j]:  # i的前置任务j在同一个组中
                    inner[group[i]][j].append(i)  # {任务组：{前置任务号：[项目号]}}
                else:
                    inter[group[j]].append(group[i])  # {前置任务号：[项目号]}
        # 以上，实现了在同一个项目组下，j->i的图建立,和不同任务下j->i的图建立

        # 3：拓扑排序
        def check_topo(g, nodes):
            """
            首先，对于有向无环图中的每个节点，使用 defaultdict(int) 创建一个名为 "indeg" 的字典，记录每个节点的入度。
            然后，遍历有向无环图中的每个节点，将与该节点相邻的节点的入度加1。
            接着，从所有入度为0的节点开始，执行拓扑排序的过程。将这些入度为0的节点存储在一个列表 "q" 中，
                并将其复制到 "topo_ans" 列表中，用于存储拓扑排序的结果。
            然后，循环遍历 "q" 列表，对于每个节点 "qq"，将与其相邻的节点 "next_node" 的入度减1，
                并将入度变为0的节点添加到 "new_q" 列表中，用于下一轮遍历。
            最后，将 "new_q" 列表赋值给 "q"，继续执行上述循环过程，直到所有节点都被遍历完毕。
                如果拓扑排序结果中的节点数与输入节点列表 "nodes" 的长度相等，则返回拓扑排序的结果，否则返回一个空列表。
            """
            indeg = defaultdict(int)
            for x in g:
                for y in g[x]: # y入度+1
                    indeg[y] += 1
            q = [i for i in nodes if indeg[i] == 0]  # 在indeg函数中，i为0时，存入
            topo_ans = q[:]
            while q:
                new_q = []
                for qq in q:
                    for next_node in g[qq]:
                        indeg[next_node] -= 1
                        if indeg[next_node] == 0:
                            topo_ans.append(next_node)
                            new_q.append(next_node)
                q = new_q
            return topo_ans if len(topo_ans) == len(nodes) else []

        # 4:组间 topo
        inter_topo = check_topo(inter,list(set(group)))
        if len(inter_topo) == 0:
            return []

        # 5:组内topo
        whole_topo = []
        for idx in inter_topo: # 按照inter_topo取出group的idx
            inner_topo = check_topo(inner[idx], groupIndex2groupMember[idx])

            if len(inner_topo) == 0:
                return []
            whole_topo.extend(inner_topo)
        return whole_topo

复杂度分析

"""
时间复杂度：O(m+n) 空间复杂度：O(m+n)

"""

[snmyj]

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        for(int i = 0; i < n; i++)
        {
            if(group[i] == -1)
                group[i] = m++;
        }
        vector<vector<int>> itemgraph(n);
        vector<vector<int>> groupgraph(m);
        vector<int> itemIndegree(n, 0);
        vector<int> groupIndegree(m, 0);
        for(int i = 0; i < n; i++)
        {
            for(auto j : beforeItems[i])
            {
                itemgraph[j].push_back(i);
                itemIndegree[i]++;
                if(group[i] != group[j]) 
                {   
                    groupgraph[group[j]].push_back(group[i]);
                    groupIndegree[group[i]]++;
                }
            }
        }
        vector<vector<int>> g_items(m);

        queue<int> q;
        for(int i = 0; i < n; i++)
            if(itemIndegree[i] == 0)
                q.push(i);
        int countItem = 0;
        while(!q.empty())
        {
            int i = q.front();
            q.pop();
            countItem++;
            g_items[group[i]].push_back(i);

            for(auto j : itemgraph[i])
            {
                if(--itemIndegree[j]==0)
                    q.push(j);
            }
        }
        if(countItem != n)
            return {};

        vector<int> g_order;
        for(int i = 0; i < m; i++)
            if(groupIndegree[i] == 0)
                q.push(i);
        int countgroup = 0;
        while(!q.empty())
        {
            int g = q.front();
            q.pop();
            countgroup++;
            g_order.push_back(g);
            for(auto j : groupgraph[g])
            {
                if(--groupIndegree[j]==0)
                    q.push(j);
            }
        }
        if(countgroup != m)
            return {};

        vector<int> ans(n);
        int idx = 0;
        for(auto g : g_order)
        {
            for(auto i : g_items[g])
                ans[idx++] = i;
        }
        return ans;
    }
};

[Bochengwan]

思路

拓扑排序

代码

public class Solution {

    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // 第 1 步：数据预处理，给没有归属于一个组的项目编上组号
        for (int i = 0; i < group.length; i++) {
            if (group[i] == -1) {
                group[i] = m;
                m++;
            }
        }

        // 第 2 步：实例化组和项目的邻接表
        List<Integer>[] groupAdj = new ArrayList[m];
        List<Integer>[] itemAdj = new ArrayList[n];
        for (int i = 0; i < m; i++) {
            groupAdj[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            itemAdj[i] = new ArrayList<>();
        }

        // 第 3 步：建图和统计入度数组
        int[] groupsIndegree = new int[m];
        int[] itemsIndegree = new int[n];

        int len = group.length;
        for (int i = 0; i < len; i++) {
            int currentGroup = group[i];
            for (int beforeItem : beforeItems.get(i)) {
                int beforeGroup = group[beforeItem];
                if (beforeGroup != currentGroup) {
                    groupAdj[beforeGroup].add(currentGroup);
                    groupsIndegree[currentGroup]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (Integer item : beforeItems.get(i)) {
                itemAdj[item].add(i);
                itemsIndegree[i]++;
            }
        }

        // 第 4 步：得到组和项目的拓扑排序结果
        List<Integer> groupsList = topologicalSort(groupAdj, groupsIndegree, m);
        if (groupsList.size() == 0) {
            return new int[0];
        }
        List<Integer> itemsList = topologicalSort(itemAdj, itemsIndegree, n);
        if (itemsList.size() == 0) {
            return new int[0];
        }

        // 第 5 步：根据项目的拓扑排序结果，项目到组的多对一关系，建立组到项目的一对多关系
        // key：组，value：在同一组的项目列表
        Map<Integer, List<Integer>> groups2Items = new HashMap<>();
        for (Integer item : itemsList) {
            groups2Items.computeIfAbsent(group[item], key -> new ArrayList<>()).add(item);
        }

        // 第 6 步：把组的拓扑排序结果替换成为项目的拓扑排序结果
        List<Integer> res = new ArrayList<>();
        for (Integer groupId : groupsList) {
            List<Integer> items = groups2Items.getOrDefault(groupId, new ArrayList<>());
            res.addAll(items);
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    private List<Integer> topologicalSort(List<Integer>[] adj, int[] inDegree, int n) {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            Integer front = queue.poll();
            res.add(front);
            for (int successor : adj[front]) {
                inDegree[successor]--;
                if (inDegree[successor] == 0) {
                    queue.offer(successor);
                }
            }
        }

        if (res.size() == n) {
            return res;
        }
        return new ArrayList<>();
    }
}

复杂度分析

• 时间复杂度：O(m+n)
• 空间复杂度：O(m+n)

[Meisgithub]

class Solution {
private:
    vector<int> topSort(vector<vector<int>>& graph, vector<int>& degree, vector<int>& items)
    {
        queue<int> q;
        for (int item : items)
        {
            if (degree[item] == 0)
            {
                q.push(item);
            }
        }
        vector<int> res;
        while (!q.empty())
        {
            int v = q.front();
            q.pop();
            res.push_back(v);
            for (int next : graph[v])
            {
                degree[next]--;
                if (degree[next] == 0)
                {
                    q.push(next);
                }
            }
        }
        return res.size() == items.size() ? res : vector<int>();
    }
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<vector<int>> groupToItems(n + m);
        int nextGroup = m;
        for (int i = 0; i < n; ++i)
        {
            if (group[i] == -1)
            {
                group[i] = nextGroup;
                nextGroup++;
            }
            groupToItems[group[i]].push_back(i);
        }

        vector<vector<int>> itemGraph(n);
        vector<vector<int>> groupGraph(n + m);
        vector<int> itemDegree(n, 0);
        vector<int> groupDegree(n + m);
        for (int i = 0; i < n; ++i)
        {
            int curGroup = group[i];
            for (int before: beforeItems[i])
            {
                int beforeGroup = group[before];
                if (curGroup == beforeGroup)
                {
                    itemGraph[before].push_back(i);
                    itemDegree[i]++;
                }
                else
                {
                    groupGraph[beforeGroup].push_back(curGroup);
                    groupDegree[curGroup]++;
                }
            }
        }

        vector<int> id(n + m);
        for (int i = 0; i < n + m; ++i)
        {
            id[i] = i;
        }
        // vector<int> ans;
        vector<int> groupSort = topSort(groupGraph, groupDegree, id);
        if (groupSort.empty())
        {
            return vector<int>();
        }
        vector<int> ans;
        for (int groupId : groupSort)
        {
            if (groupToItems[groupId].empty())
            {
                continue;
            }
            vector<int> partSort = topSort(itemGraph, itemDegree, groupToItems[groupId]);
            if (partSort.empty())
            {
                return vector<int>();
            }
            for (int item : partSort)
            {
                ans.push_back(item);
            }
        }
        return ans;
    }
};

[joemonkeylee]

思路

没。读懂题 。。

代码

   public int[] SortItems(int n, int m, int[] group, IList<IList<int>> beforeItems)
        {
            for (int i = 0; i < n; i++)
            {
                if (group[i] < 0)
                {
                    group[i] = m;
                    m++;
                }
            }
            IList<int>[] groupItems = new IList<int>[m];
            for (int i = 0; i < m; i++)
            {
                groupItems[i] = new List<int>();
            }
            int[] groupIndegrees = new int[m];
            int[] itemIndegrees = new int[n];
            IList<int>[] groupNextArr = new IList<int>[m];
            for (int i = 0; i < m; i++)
            {
                groupNextArr[i] = new List<int>();
            }
            IList<int>[] itemNextArr = new IList<int>[n];
            for (int i = 0; i < n; i++)
            {
                itemNextArr[i] = new List<int>();
            }
            for (int i = 0; i < n; i++)
            {
                int currGroup = group[i];
                groupItems[currGroup].Add(i);
                IList<int> before = beforeItems[i];
                foreach (int j in before)
                {
                    int prevGroup = group[j];
                    if (prevGroup == currGroup)
                    {
                        itemIndegrees[i]++;
                        itemNextArr[j].Add(i);
                    }
                    else
                    {
                        groupIndegrees[currGroup]++;
                        groupNextArr[prevGroup].Add(currGroup);
                    }
                }
            }
            IList<int> groupList = new List<int>();
            for (int i = 0; i < m; i++)
            {
                groupList.Add(i);
            }
            int[] groupsOrder = TopologicalSort(groupIndegrees, groupNextArr, groupList);
            if (groupsOrder.Length != groupList.Count)
            {
                return new int[0];
            }
            int[] itemsOrder = new int[n];
            int itemIndex = 0;
            for (int i = 0; i < m; i++)
            {
                IList<int> items = groupItems[groupsOrder[i]];
                int[] groupItemsOrder = TopologicalSort(itemIndegrees, itemNextArr, items);
                int currCount = groupItemsOrder.Length;
                if (currCount != items.Count)
                {
                    return new int[0];
                }
                Array.Copy(groupItemsOrder, 0, itemsOrder, itemIndex, currCount);
                itemIndex += currCount;
            }
            return itemsOrder;
        }

        public int[] TopologicalSort(int[] indegrees, IList<int>[] nextArr, IList<int> nums)
        {
            int count = nums.Count;
            int[] order = new int[count];
            int index = 0;
            Queue<int> queue = new Queue<int>();
            foreach (int num in nums)
            {
                if (indegrees[num] == 0)
                {
                    queue.Enqueue(num);
                }
            }
            while (queue.Count > 0)
            {
                int curr = queue.Dequeue();
                order[index] = curr;
                index++;
                IList<int> nextList = nextArr[curr];
                foreach (int next in nextList)
                {
                    indegrees[next]--;
                    if (indegrees[next] == 0)
                    {
                        queue.Enqueue(next);
                    }
                }
            }
            return index == count ? order : new int[0];
        }

复杂度分析

• 时间复杂度：O(n+m+k)
• 空间复杂度：O(n+m+k)

[xiaoq777]

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        for(int i = 0; i < group.length; i++) {
            if(group[i] == -1) {
                group[i] = m;
                m += 1;
            }
        }

        List<List<Integer>> groupGraph = new ArrayList<>();
        List<List<Integer>> itemsGraph = new ArrayList<>();
        for(int i = 0; i < m; i++) {
            groupGraph.add(new ArrayList<>());
        }
        for(int i = 0; i < n; i++) {
            itemsGraph.add(new ArrayList<>());
        }
        int[] groupInDegree = new int[m];
        for(int i = 0; i < beforeItems.size(); i++) {
            int curGroup = group[i];
            for(Integer j : beforeItems.get(i)) {
                if (curGroup != group[j]) {
                    groupGraph.get(group[j]).add(curGroup);
                    groupInDegree[curGroup] += 1;
                }
            }
        }

        int[] itemsInDegree = new int[n];
        for(int i = 0; i < beforeItems.size(); i++) {
            for(int j : beforeItems.get(i)) {
                itemsGraph.get(j).add(i);
                itemsInDegree[i] += 1;
            }
        }

        List<Integer> groupSorted = topologicalSort(groupGraph, groupInDegree, m);
        List<Integer> itemsSorted = topologicalSort(itemsGraph, itemsInDegree, n);
        if(groupSorted == null || itemsSorted == null) {
            return new int[0];
        }

        Map<Integer, List<Integer>> groupItemsMap = new HashMap<>();
        for(int i = 0; i < itemsSorted.size(); i++) {
            groupItemsMap.computeIfAbsent(group[itemsSorted.get(i)], k -> new ArrayList<>()).add(itemsSorted.get(i));
        }
        int[] result = new int[n];
        int j = 0;
        for(int i = 0; i < groupSorted.size(); i++) {
            List<Integer> list = groupItemsMap.get(groupSorted.get(i));
            if(list == null) {
                continue;
            }
            for(int k : list) {
                result[j++] = k;
            }
        }
        return result;
    }

    private static List<Integer> topologicalSort(List<List<Integer>> graph, int[] inDegree, int l) {
        int len = inDegree.length;
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < len; i++) {
            if(inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        List<Integer> result = new ArrayList<>();
        while(!queue.isEmpty()) {
            int i = queue.poll();
            result.add(i);
            for(Integer j : graph.get(i)) {
                inDegree[j] -= 1;
                if(inDegree[j] == 0) {
                    queue.offer(j);
                }
            }
        }
        if(result.size() != l) {
            return null;
        }
        return result;
    }
}

[AstrKing]

思路

图，讲道理，自己没想出来，先提交作业了，后面自己再好好看下

代码

public class Solution {

    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // 第 1 步：数据预处理，给没有归属于一个组的项目编上组号
        for (int i = 0; i < group.length; i++) {
            if (group[i] == -1) {
                group[i] = m;
                m++;
            }
        }

        // 第 2 步：实例化组和项目的邻接表
        List<Integer>[] groupAdj = new ArrayList[m];
        List<Integer>[] itemAdj = new ArrayList[n];
        for (int i = 0; i < m; i++) {
            groupAdj[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            itemAdj[i] = new ArrayList<>();
        }

        // 第 3 步：建图和统计入度数组
        int[] groupsIndegree = new int[m];
        int[] itemsIndegree = new int[n];

        int len = group.length;
        for (int i = 0; i < len; i++) {
            int currentGroup = group[i];
            for (int beforeItem : beforeItems.get(i)) {
                int beforeGroup = group[beforeItem];
                if (beforeGroup != currentGroup) {
                    groupAdj[beforeGroup].add(currentGroup);
                    groupsIndegree[currentGroup]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (Integer item : beforeItems.get(i)) {
                itemAdj[item].add(i);
                itemsIndegree[i]++;
            }
        }

        // 第 4 步：得到组和项目的拓扑排序结果
        List<Integer> groupsList = topologicalSort(groupAdj, groupsIndegree, m);
        if (groupsList.size() == 0) {
            return new int[0];
        }
        List<Integer> itemsList = topologicalSort(itemAdj, itemsIndegree, n);
        if (itemsList.size() == 0) {
            return new int[0];
        }

        // 第 5 步：根据项目的拓扑排序结果，项目到组的多对一关系，建立组到项目的一对多关系
        // key：组，value：在同一组的项目列表
        Map<Integer, List<Integer>> groups2Items = new HashMap<>();
        for (Integer item : itemsList) {
            groups2Items.computeIfAbsent(group[item], key -> new ArrayList<>()).add(item);
        }

        // 第 6 步：把组的拓扑排序结果替换成为项目的拓扑排序结果
        List<Integer> res = new ArrayList<>();
        for (Integer groupId : groupsList) {
            List<Integer> items = groups2Items.getOrDefault(groupId, new ArrayList<>());
            res.addAll(items);
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    private List<Integer> topologicalSort(List<Integer>[] adj, int[] inDegree, int n) {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            Integer front = queue.poll();
            res.add(front);
            for (int successor : adj[front]) {
                inDegree[successor]--;
                if (inDegree[successor] == 0) {
                    queue.offer(successor);
                }
            }
        }

        if (res.size() == n) {
            return res;
        }
        return new ArrayList<>();
    }
}

复杂度分析

时间复杂度：O(m+n)

空间复杂度：O(m+n)

[wangzh0114]

class Solution {
public:
    vector<int> topologicalSort(vector<vector<int>> &Adj, vector<int> &Indegree, int n){
        vector<int> res;
        queue<int> q;
        for(int i = 0;i<n;i++){
            if(Indegree[i]==0){
                q.push(i);
            }
        }
        while(!q.empty()){
            int front = q.front();
            q.pop();
            res.push_back(front);
            for(int successor: Adj[front]){
                Indegree[successor]--;
                if(Indegree[successor]==0){
                    q.push(successor);
                }
            }
        }
        if(res.size()==n){return res;}
        return vector<int>();
    }
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        // 第 1 步：数据预处理，给没有归属于一个组的项目编上组号
        for(int i=0;i<group.size();i++){
            if(group[i] == -1){
                group[i] = m;
                m++;
            }
        }
        // 第 2 步：实例化组和项目的邻接表
        vector<vector<int>> groupAdj(m, vector<int>());
        vector<vector<int>> itemAdj(n, vector<int>());

        // 第 3 步：建图和统计入度数组
        vector<int> groupsIndegree(m, 0);
        vector<int> itemIndegree(n, 0);

        int len = group.size();
        for(int i=0;i<len;i++){
            int currentGroup = group[i];
            for(int beforeItem: beforeItems[i]){
                int beforeGroup = group[beforeItem];
                if(beforeGroup!=currentGroup){
                    groupAdj[beforeGroup].push_back(currentGroup);
                    groupsIndegree[currentGroup]++;
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int item: beforeItems[i]){
                itemAdj[item].push_back(i);
                itemIndegree[i]++;
            }
        }
        // 第 4 步：得到组和项目的拓扑排序结果
        vector<int> groupList = topologicalSort(groupAdj, groupsIndegree, m);
        if(groupList.size()==0){
            return vector<int> ();
        }
        vector<int> itemList = topologicalSort(itemAdj, itemIndegree, n);
        if(itemList.size()==0){
            return vector<int> ();
        }
        // 第 5 步：根据项目的拓扑排序结果，项目到组的多对一关系，建立组到项目的一对多关系
        // key：组，value：在同一组的项目列表
        map<int, vector<int>> group2Items;
        for(int item: itemList){
            group2Items[group[item]].push_back(item);
        }
        // 第 6 步：把组的拓扑排序结果替换成为项目的拓扑排序结果
        vector<int> res;
        for(int groupId: groupList){
            vector<int> items = group2Items[groupId];
            for(int item: items){
                res.push_back(item);
            }
        }
        return res;
    } 
};

[jiujingxukong]

今天没工夫写了

[Lydia61]

1203. 项目管理

思路

官方拓扑排序

代码

class Solution {
public:
    vector<int> topSort(vector<int>& deg, vector<vector<int>>& graph, vector<int>& items) {
        queue<int> Q;
        for (auto& item: items) {
            if (deg[item] == 0) {
                Q.push(item);
            }
        }
        vector<int> res;
        while (!Q.empty()) {
            int u = Q.front(); 
            Q.pop();
            res.emplace_back(u);
            for (auto& v: graph[u]) {
                if (--deg[v] == 0) {
                    Q.push(v);
                }
            }
        }
        return res.size() == items.size() ? res : vector<int>{};
    }

    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<vector<int>> groupItem(n + m);

        // 组间和组内依赖图
        vector<vector<int>> groupGraph(n + m);
        vector<vector<int>> itemGraph(n);

        // 组间和组内入度数组
        vector<int> groupDegree(n + m, 0);
        vector<int> itemDegree(n, 0);

        vector<int> id;
        for (int i = 0; i < n + m; ++i) {
            id.emplace_back(i);
        }

        int leftId = m;
        // 给未分配的 item 分配一个 groupId
        for (int i = 0; i < n; ++i) {
            if (group[i] == -1) {
                group[i] = leftId;
                leftId += 1;
            }
            groupItem[group[i]].emplace_back(i);
        }
        // 依赖关系建图
        for (int i = 0; i < n; ++i) {
            int curGroupId = group[i];
            for (auto& item: beforeItems[i]) {
                int beforeGroupId = group[item];
                if (beforeGroupId == curGroupId) {
                    itemDegree[i] += 1;
                    itemGraph[item].emplace_back(i);   
                } else {
                    groupDegree[curGroupId] += 1;
                    groupGraph[beforeGroupId].emplace_back(curGroupId);
                }
            }
        }

        // 组间拓扑关系排序
        vector<int> groupTopSort = topSort(groupDegree, groupGraph, id); 
        if (groupTopSort.size() == 0) {
            return vector<int>{};
        } 
        vector<int> ans;
        // 组内拓扑关系排序
        for (auto& curGroupId: groupTopSort) {
            int size = groupItem[curGroupId].size();
            if (size == 0) {
                continue;
            }
            vector<int> res = topSort(itemDegree, itemGraph, groupItem[curGroupId]);
            if (res.size() == 0) {
                return vector<int>{};
            }
            for (auto& item: res) {
                ans.emplace_back(item);
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(m+n)
• 空间复杂度：O(m+n)

[kangliqi1]

public int[] SortItems(int n, int m, int[] group, IList<IList> beforeItems) { for (int i = 0; i < n; i++) { if (group[i] < 0) { group[i] = m; m++; } } IList[] groupItems = new IList[m]; for (int i = 0; i < m; i++) { groupItems[i] = new List(); } int[] groupIndegrees = new int[m]; int[] itemIndegrees = new int[n]; IList[] groupNextArr = new IList[m]; for (int i = 0; i < m; i++) { groupNextArr[i] = new List(); } IList[] itemNextArr = new IList[n]; for (int i = 0; i < n; i++) { itemNextArr[i] = new List(); } for (int i = 0; i < n; i++) { int currGroup = group[i]; groupItems[currGroup].Add(i); IList before = beforeItems[i]; foreach (int j in before) { int prevGroup = group[j]; if (prevGroup == currGroup) { itemIndegrees[i]++; itemNextArr[j].Add(i); } else { groupIndegrees[currGroup]++; groupNextArr[prevGroup].Add(currGroup); } } } IList groupList = new List(); for (int i = 0; i < m; i++) { groupList.Add(i); } int[] groupsOrder = TopologicalSort(groupIndegrees, groupNextArr, groupList); if (groupsOrder.Length != groupList.Count) { return new int[0]; } int[] itemsOrder = new int[n]; int itemIndex = 0; for (int i = 0; i < m; i++) { IList items = groupItems[groupsOrder[i]]; int[] groupItemsOrder = TopologicalSort(itemIndegrees, itemNextArr, items); int currCount = groupItemsOrder.Length; if (currCount != items.Count) { return new int[0]; } Array.Copy(groupItemsOrder, 0, itemsOrder, itemIndex, currCount); itemIndex += currCount; } return itemsOrder; }

    public int[] TopologicalSort(int[] indegrees, IList<int>[] nextArr, IList<int> nums)
    {
        int count = nums.Count;
        int[] order = new int[count];
        int index = 0;
        Queue<int> queue = new Queue<int>();
        foreach (int num in nums)
        {
            if (indegrees[num] == 0)
            {
                queue.Enqueue(num);
            }
        }
        while (queue.Count > 0)
        {
            int curr = queue.Dequeue();
            order[index] = curr;
            index++;
            IList<int> nextList = nextArr[curr];
            foreach (int next in nextList)
            {
                indegrees[next]--;
                if (indegrees[next] == 0)
                {
                    queue.Enqueue(next);
                }
            }
        }
        return index == count ? order : new int[0];
    }

[yingchehu]

嘗試讀懂

class Solution:
    # bfs topological sort
    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
    # 從 indegree 0 的節點開始
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
        # 走過相連節點將 indegree 減一
                indegree[neighbor] -= 1
        # 直到 indegree 為 0 時加入 queue
                if not indegree[neighbor]:
                    q.append(neighbor)

        return ans

    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
        max_group_id = m
    # 沒有小組負責的專案，逕自逐一分配給新的小組
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = collections.defaultdict(int)
        group_indegree = collections.defaultdict(int)
        project_neighbors = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        group_projects = collections.defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for pre in pres[project]:
        # 如果是不同小組完成的，那這兩個小組就有相依關係
                if group[pre] != group[project]:
                    # 小组關係圖
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    # 專案關係圖
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)

        ans = []
        # 先對小組做拓墣排序
        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []

        for group_id in group_queue:
            # 對小組中的專案做拓墣排序
            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans += project_queue

        return ans

[linlizzz]

没做出来，看了题解，需要先对组进行一次拓扑排序，然后对项目进行拓扑排序，还是需要好好消化一下

class Solution:
    # 拓扑排序
    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)

        return ans

    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
        max_group_id = m
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = collections.defaultdict(int)
        group_indegree = collections.defaultdict(int)
        project_neighbors = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        group_projects = collections.defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for pre in pres[project]:
                if group[pre] != group[project]:
                    # 小组关系图
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    # 项目关系图
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)

        ans = []
        # 先对组进行拓扑排序
        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []

        for group_id in group_queue:
            # 对小组中的项目进行拓扑排序
            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans += project_queue

        return ans

复杂度：

T(n) = O(m+n)

S(n) = O(m+n)

[lp1506947671]

Python3：

class Solution:
    # 拓扑排序
    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)

        return ans

    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
        max_group_id = m
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = collections.defaultdict(int)
        group_indegree = collections.defaultdict(int)
        project_neighbors = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        group_projects = collections.defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for pre in pres[project]:
                if group[pre] != group[project]:
                    # 小组关系图
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    # 项目关系图
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)

        ans = []
        # 先对组进行拓扑排序
        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []

        for group_id in group_queue:
            # 对小组中的项目进行拓扑排序
            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans += project_queue

        return ans

复杂度分析

令 m 和 n 分别为图的边数和顶点数。

• 时间复杂度：O(m + n)O(m+n)
• 空间复杂度：O(m + n)O(m+n)

[Jetery]

class Solution {
public:
    vector<int> topSort(vector<int> &deg, vector<vector<int>> &graph, vector<int> &items) {
        queue<int> q;
        for (auto item : items) {
            if (deg[item] == 0) q.push(item);
        }
        vector<int> ret;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            ret.push_back(u);
            for (auto &v : graph[u]) {
                if (--deg[v] == 0) q.push(v);
            }
        }
        return ret.size() == items.size() ? ret : vector<int> {};
    }
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<vector<int>> groupItem(n + m);

        vector<vector<int>> groupGraph(n + m);
        vector<vector<int>> itemGraph(n);

        vector<int> groupDegree(n + m, 0);
        vector<int> itemDegree(n, 0);

        vector<int> id;
        for (int i = 0; i < n + m; i++) {
            id.push_back(i);
        }

        int leftId = m;
        for (int i = 0; i < n; i++) {
            if (group[i] == -1) {
                group[i] = leftId;
                leftId += 1;
            }
            groupItem[group[i]].push_back(i);
        }

        for (int i = 0; i < n; ++i) {
            int curGroupId = group[i];
            for (auto& item: beforeItems[i]) {

                int beforeGroupId = group[item];
                if (beforeGroupId == curGroupId) {
                    itemDegree[i] += 1;
                    itemGraph[item].push_back(i);   
                } else {
                    groupDegree[curGroupId] += 1;
                    groupGraph[beforeGroupId].push_back(curGroupId);
                }
            }
        }

        // 组间拓扑关系排序
        vector<int> groupTopSort = topSort(groupDegree, groupGraph, id); 
        if (groupTopSort.size() == 0) {
            return vector<int>{};
        } 
        vector<int> ans;

        // 组内拓扑关系排序
        for (auto& curGroupId: groupTopSort) {
            int size = groupItem[curGroupId].size();
            if (size == 0) {
                continue;
            }
            //按组的topo序逐个进行内部排序
            vector<int> res = topSort(itemDegree, itemGraph, groupItem[curGroupId]);
            if (res.size() == 0) {
                return vector<int>{};
            }
            for (auto& item: res) {
                ans.push_back(item);
            }
        }
        return ans;

    }
};

[for123s]

class Solution {
public:
    vector<int> topologicalSort(vector<vector<int>> &Adj, vector<int> &Indegree, int n){
        vector<int> res;
        queue<int> q;
        for(int i = 0;i<n;i++){
            if(Indegree[i]==0){
                q.push(i);
            }
        }
        while(!q.empty()){
            int front = q.front();
            q.pop();
            res.push_back(front);
            for(int successor: Adj[front]){
                Indegree[successor]--;
                if(Indegree[successor]==0){
                    q.push(successor);
                }
            }
        }
        if(res.size()==n){return res;}
        return vector<int>();
    }
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        // 第 1 步：数据预处理，给没有归属于一个组的项目编上组号
        for(int i=0;i<group.size();i++){
            if(group[i] == -1){
                group[i] = m;
                m++;
            }
        }
        // 第 2 步：实例化组和项目的邻接表
        vector<vector<int>> groupAdj(m, vector<int>());
        vector<vector<int>> itemAdj(n, vector<int>());

        // 第 3 步：建图和统计入度数组
        vector<int> groupsIndegree(m, 0);
        vector<int> itemIndegree(n, 0);

        int len = group.size();
        for(int i=0;i<len;i++){
            int currentGroup = group[i];
            for(int beforeItem: beforeItems[i]){
                int beforeGroup = group[beforeItem];
                if(beforeGroup!=currentGroup){
                    groupAdj[beforeGroup].push_back(currentGroup);
                    groupsIndegree[currentGroup]++;
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int item: beforeItems[i]){
                itemAdj[item].push_back(i);
                itemIndegree[i]++;
            }
        }
        // 第 4 步：得到组和项目的拓扑排序结果
        vector<int> groupList = topologicalSort(groupAdj, groupsIndegree, m);
        if(groupList.size()==0){
            return vector<int> ();
        }
        vector<int> itemList = topologicalSort(itemAdj, itemIndegree, n);
        if(itemList.size()==0){
            return vector<int> ();
        }
        // 第 5 步：根据项目的拓扑排序结果，项目到组的多对一关系，建立组到项目的一对多关系
        // key：组，value：在同一组的项目列表
        map<int, vector<int>> group2Items;
        for(int item: itemList){
            group2Items[group[item]].push_back(item);
        }
        // 第 6 步：把组的拓扑排序结果替换成为项目的拓扑排序结果
        vector<int> res;
        for(int groupId: groupList){
            vector<int> items = group2Items[groupId];
            for(int item: items){
                res.push_back(item);
            }
        }
        return res;
    } 
};

[X1AOX1A]

class Solution:
    # 拓扑排序
    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)

        return ans

    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
        max_group_id = m
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = collections.defaultdict(int)
        group_indegree = collections.defaultdict(int)
        project_neighbors = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        group_projects = collections.defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for pre in pres[project]:
                if group[pre] != group[project]:
                    # 小组关系图
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    # 项目关系图
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)

        ans = []
        # 先对组进行拓扑排序
        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []

        for group_id in group_queue:
            # 对小组中的项目进行拓扑排序
            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans += project_queue

        return ans

[zpbc007]

思路

• 通过 item 之间的依赖关系推导出 group 之间的依赖关系
• 计算 item、group 的拓扑排序结果
• 建立 group 与 item 的多对一关系
• 按 item 的拓扑顺序设置 group 的值
• 按 group 的拓扑顺序输出结果

代码

function sortItems(
    n: number,
    m: number,
    group: number[],
    beforeItems: number[][],
): number[] {
    // 把 groupId 为 -1 的项目，标记为不同的 group
    group.forEach((groupId, index) => {
        if (groupId === -1) {
            group[index] = m++
        }
    })

    // 初始化 group 和 item 的图
    const groupGraph: number[][] = []
    for (let i = 0; i < m; i++) {
        groupGraph[i] = []
    }

    const itemGraph: number[][] = []
    for (let i = 0; i < n; i++) {
        itemGraph[i] = []
    }

    // 建图 & 计算入度
    const groupsIndegree: number[] = new Array(m).fill(0)
    const itemsIndegree: number[] = new Array(n).fill(0)
    for (let i = 0; i < group.length; i++) {
        const currentGroup = group[i]

        for (const beforeItem of beforeItems[i]) {
            const beforeGroup = group[beforeItem]

            if (beforeGroup !== currentGroup) {
                groupGraph[beforeGroup].push(currentGroup)
                groupsIndegree[currentGroup]++
            }
        }
    }

    beforeItems.forEach((beforeItem, i) => {
        beforeItem.forEach((item) => {
            itemGraph[item].push(i)
            itemsIndegree[i]++
        })
    })

    const groupList = topologicalSort(groupGraph, groupsIndegree)
    if (!groupList) {
        return []
    }

    const itemList = topologicalSort(itemGraph, itemsIndegree)
    if (!itemList) {
        return []
    }

    // 建立 group 与 item 的关系
    const group2Item = new Map<number, number[]>()
    // 每个 group 的 item 列表都满足拓扑排序
    itemList.forEach((itemId) => {
        const groupId = group[itemId]
        if (!group2Item.has(groupId)) {
            group2Item.set(groupId, [])
        }
        group2Item.get(groupId)!.push(itemId)
    })

    // 按 group 的拓扑排序输出结果
    return groupList.reduce<number[]>((result, groupId) => {
        return result.concat(group2Item.get(groupId) || [])
    }, [])
}

function topologicalSort(graph: number[][], indegree: number[]): null | number[] {
    const queue: number[] = []
    const result: number[] = []

    // 入度为 0 的节点放入队列
    for (let i = 0; i < indegree.length; i++) {
        if (indegree[i] === 0) {
            queue.push(i)
        }
    }

    while (queue.length) {
        const node = queue.shift()!
        result.push(node)

        for (let nextNode of graph[node]) {
            indegree[nextNode]--
            if (indegree[nextNode] === 0) {
                queue.push(nextNode)
            }
        }
    }

    if (result.length !== indegree.length) {
        return null
    }

    return result
}

复杂度

• 时间复杂度：O(m + n^2)
• 空间复杂度：O(m + n^2)

[JadeLiu13]

from collections import defaultdict

` class Solution: def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:

将不属于任何组的单独成组赋予组编号并记录每个组的成员

    dct = defaultdict(list)
    for i in range(n):
        if group[i] == -1:
            group[i] = m
            m += 1
        dct[group[i]].append(i)
    # 记录组间的拓扑关系与组内的拓扑关系
    inter_edge = defaultdict(list)
    inner_edge = defaultdict(lambda: defaultdict(list))
    for i in range(n):
        for j in beforeItems[i]:
            if group[i] == group[j]:
                inner_edge[group[i]][j].append(i)
            else:
                inter_edge[group[j]].append(group[i])
    # 检查网络拓扑是否可行
    def check(edge, nodes):
        degree = defaultdict(int)
        for j in edge:
            for i in edge[j]:
                degree[i] += 1
        ans = []
        stack = [i for i in nodes if not degree[i]]
        while stack:
            ans.extend(stack)
            nex = []
            for j in stack:
                for i in edge[j]:
                    degree[i] -= 1
                    if not degree[i]:
                        nex.append(i)
            stack = nex[:]
        return ans if len(ans) == len(nodes) else []

    # 确定组间的可行顺序
    inter_order = check(inter_edge, list(set(group)))
    if not inter_order:
        return inter_order
    # 确定组内的可行的顺序        
    res = []
    for g in inter_order:
        inner_order = check(inner_edge[g], dct[g])
        if not inner_order:
            return inner_order
        res.extend(inner_order)
    return res

`

参考

链接：https://leetcode.cn/problems/sort-items-by-groups-respecting-dependencies/solution/er-xu-cheng-ming-jiu-xu-zui-by-liupengsa-e2f3/