rust 解法, 执行用时: 12 ms, 内存消耗: 5.3 MB, 提交时间: 2023-09-22 09:55:00

impl Solution {
    pub fn sort_items(
        n: i32, m: i32, 
        group: Vec<i32>, 
        before_items: Vec<Vec<i32>>) -> Vec<i32> {
        
        let mut result = vec![];
        let mut graph = vec![vec![]; (n + m) as usize];
        let mut in_degree = vec![0; (n + m) as usize];

        for i in 0..group.len() {
            if group[i] == -1 {
                continue;
            }
            graph[(n + group[i]) as usize].push(i as i32);
            in_degree[i] += 1;
        }

        for i in 0..before_items.len() {
            for &item in &before_items[i] {
                let rep_before_item = if group[item as usize] == -1 {
                    item
                } else {
                    n + group[item as usize]
                };
                let rep_current_item = if group[i] == -1 {
                    i as i32
                } else {
                    n + group[i]
                };

                if rep_before_item == rep_current_item {
                    graph[item as usize].push(i as i32);
                    in_degree[i] += 1;
                } else {
                    graph[rep_before_item as usize].push(rep_current_item);
                    in_degree[rep_current_item as usize] += 1;
                }
            }
        }

        for i in 0..n + m {
            if in_degree[i as usize] == 0 {
                Self::dfs(&mut graph, &mut in_degree, i, n, &mut result);
            }
        }
        if result.len() as i32 == n {
            result
        } else {
            vec![]
        }
    }

    // dfs 拓扑排序
    pub fn dfs(
        graph: &mut Vec<Vec<i32>>,
        in_degree: &mut Vec<i32>,
        cur: i32,
        n: i32,
        res: &mut Vec<i32>,
    ) {
        if cur < n {
            res.push(cur);
        }
        in_degree[cur as usize] -= 1;

        for &child in &graph[cur as usize].clone() {
            in_degree[child as usize] -= 1;
            if in_degree[child as usize] == 0 {
                Self::dfs(graph, in_degree, child, n, res);
            }
        }
    }
}

golang 解法, 执行用时: 72 ms, 内存消耗: 17.9 MB, 提交时间: 2023-09-22 09:53:31

func topSort(graph [][]int, deg, items []int) (orders []int) {
    q := []int{}
    for _, i := range items {
        if deg[i] == 0 {
            q = append(q, i)
        }
    }
    for len(q) > 0 {
        from := q[0]
        q = q[1:]
        orders = append(orders, from)
        for _, to := range graph[from] {
            deg[to]--
            if deg[to] == 0 {
                q = append(q, to)
            }
        }
    }
    return
}

func sortItems(n, m int, group []int, beforeItems [][]int) (ans []int) {
    groupItems := make([][]int, m+n) // groupItems[i] 表示第 i 个组负责的项目列表
    for i := range group {
        if group[i] == -1 {
            group[i] = m + i // 给不属于任何组的项目分配一个组
        }
        groupItems[group[i]] = append(groupItems[group[i]], i)
    }

    groupGraph := make([][]int, m+n) // 组间依赖关系
    groupDegree := make([]int, m+n)
    itemGraph := make([][]int, n) // 组内依赖关系
    itemDegree := make([]int, n)
    for cur, items := range beforeItems {
        curGroupID := group[cur]
        for _, pre := range items {
            preGroupID := group[pre]
            if preGroupID != curGroupID { // 不同组项目，确定组间依赖关系
                groupGraph[preGroupID] = append(groupGraph[preGroupID], curGroupID)
                groupDegree[curGroupID]++
            } else { // 同组项目，确定组内依赖关系
                itemGraph[pre] = append(itemGraph[pre], cur)
                itemDegree[cur]++
            }
        }
    }

    // 组间拓扑序
    items := make([]int, m+n)
    for i := range items {
        items[i] = i
    }
    groupOrders := topSort(groupGraph, groupDegree, items)
    if len(groupOrders) < len(items) {
        return nil
    }

    // 按照组间的拓扑序，依次求得各个组的组内拓扑序，构成答案
    for _, groupID := range groupOrders {
        items := groupItems[groupID]
        orders := topSort(itemGraph, itemDegree, items)
        if len(orders) < len(items) {
            return nil
        }
        ans = append(ans, orders...)
    }
    return
}

cpp 解法, 执行用时: 108 ms, 内存消耗: 76.3 MB, 提交时间: 2023-09-22 09:53:02

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;
    }
};

javascript 解法, 执行用时: 7520 ms, 内存消耗: 71.8 MB, 提交时间: 2023-09-22 09:52:16

/**
 * @param {number} n
 * @param {number} m
 * @param {number[]} group
 * @param {number[][]} beforeItems
 * @return {number[]}
 */
const topSort = (deg, graph, items) => {
    const Q = [];
    for (const item of items) {
        if (deg[item] === 0) {
            Q.push(item);
        }
    }
    const res = [];
    while (Q.length) {
        const u = Q.shift(); 
        res.push(u);
        for (let i = 0; i < graph[u].length; ++i) {
            const v = graph[u][i];
            if (--deg[v] === 0) {
                Q.push(v);
            }
        }
    }
    return res.length == items.length ? res : [];
}

var sortItems = function(n, m, group, beforeItems) {
    const groupItem = new Array(n + m).fill(0).map(() => []);

    // 组间和组内依赖图
    const groupGraph = new Array(n + m).fill(0).map(() => []);
    const itemGraph = new Array(n).fill(0).map(() => []);

    // 组间和组内入度数组
    const groupDegree = new Array(n + m).fill(0);
    const itemDegree = new Array(n).fill(0);
    
    const id = new Array(n + m).fill(0).map((v, index) => index);

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

    // 组间拓扑关系排序
    const groupTopSort = topSort(groupDegree, groupGraph, id); 
    if (groupTopSort.length == 0) {
        return [];
    } 
    const ans = [];
    // 组内拓扑关系排序
    for (const curGroupId of groupTopSort) {
        const size = groupItem[curGroupId].length;
        if (size == 0) {
            continue;
        }
        const res = topSort(itemDegree, itemGraph, groupItem[curGroupId]);
        if (res.length === 0) {
            return [];
        }
        for (const item of res) {
            ans.push(item);
        }
    }
    return ans;
};

java 解法, 执行用时: 30 ms, 内存消耗: 61.8 MB, 提交时间: 2023-09-22 09:51:57

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        List<List<Integer>> groupItem = new ArrayList<List<Integer>>();
        for (int i = 0; i < n + m; ++i) {
            groupItem.add(new ArrayList<Integer>());
        }

        // 组间和组内依赖图
        List<List<Integer>> groupGraph = new ArrayList<List<Integer>>();
        for (int i = 0; i < n + m; ++i) {
            groupGraph.add(new ArrayList<Integer>());
        }
        List<List<Integer>> itemGraph = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; ++i) {
            itemGraph.add(new ArrayList<Integer>());
        }

        // 组间和组内入度数组
        int[] groupDegree = new int[n + m];
        int[] itemDegree = new int[n];
        
        List<Integer> id = new ArrayList<Integer>();
        for (int i = 0; i < n + m; ++i) {
            id.add(i);
        }

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

        // 组间拓扑关系排序
        List<Integer> groupTopSort = topSort(groupDegree, groupGraph, id); 
        if (groupTopSort.size() == 0) {
            return new int[0];
        }
        int[] ans = new int[n];
        int index = 0;
        // 组内拓扑关系排序
        for (int curGroupId : groupTopSort) {
            int size = groupItem.get(curGroupId).size();
            if (size == 0) {
                continue;
            }
            List<Integer> res = topSort(itemDegree, itemGraph, groupItem.get(curGroupId));
            if (res.size() == 0) {
                return new int[0];
            }
            for (int item : res) {
                ans[index++] = item;
            }
        }
        return ans;
    }

    public List<Integer> topSort(int[] deg, List<List<Integer>> graph, List<Integer> items) {
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int item : items) {
            if (deg[item] == 0) {
                queue.offer(item);
            }
        }
        List<Integer> res = new ArrayList<Integer>();
        while (!queue.isEmpty()) {
            int u = queue.poll(); 
            res.add(u);
            for (int v : graph.get(u)) {
                if (--deg[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        return res.size() == items.size() ? res : new ArrayList<Integer>();
    }
}

java 解法, 执行用时: 33 ms, 内存消耗: 55 MB, 提交时间: 2023-09-22 09:51:17

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

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<>();
    }
}

cpp 解法, 执行用时: 76 ms, 内存消耗: 44.5 MB, 提交时间: 2023-09-22 09:50:48

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        for (int &g : group) if (g == -1) g = m++;   // 给没有对应组的项目编号
        vector<int> groupInD(m), itemInD(n);    // 入度
        vector<vector<int>> groupAdj(m), itemAdj(n);    // 邻接表
        for (int i = 0; i < n; i++) {   // 建立入度表和邻接表
            int curGroup = group[i];
            for (int beforeItem : beforeItems[i]) {
                int beforeGroup = group[beforeItem];
                if (beforeGroup != curGroup) {
                    groupAdj[beforeGroup].emplace_back(curGroup);
                    groupInD[curGroup]++;
                } 
                itemAdj[beforeItem].emplace_back(i);
                itemInD[i]++;
            }
        }
        vector<int> groupList = topologicalSort(groupAdj, groupInD, m);
        if (groupList.empty()) return vector<int>{}; // 组间存在环、不符合要求

        vector<int> itemList = topologicalSort(itemAdj, itemInD, n);
        if (itemList.empty()) return vector<int>{}; // 项目间存在环、不符合要求

        vector<vector<int>> group2Item(m);      // 保存每个组内项目的拓扑序列
        for (int item : itemList) {
            group2Item[group[item]].emplace_back(item);
        }
        vector<int> res;
        for (int g : groupList) {   // 按照组的拓扑序列依次添加组内的项目
            res.insert(res.end(), group2Item[g].begin(), group2Item[g].end());
        }
        return res;
    }

    vector<int> topologicalSort(vector<vector<int>> &Adj, vector<int> &inD, int n) {
        queue<int> q;
        vector<int> res;
        for (int i = 0; i < n; i++) 
            if (inD[i] == 0) { q.push(i); res.emplace_back(i); }
        
        while (!q.empty()) {
            int u = q.front();  q.pop();
            for (int v : Adj[u]) {
                if (--inD[v] == 0) { q.push(v), res.emplace_back(v); }
            }
        }
        return res.size() == n ? res : vector<int>{};
    }
};

python3 解法, 执行用时: 208 ms, 内存消耗: 40.3 MB, 提交时间: 2023-09-22 09:50:05

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