題目網址：https://leetcode.cn/problems/sort-items-by-groups-respecting-dependencies/

題意：有 n 個 item, 其中每個 item 可以不屬於任何 group, 或者屬於 m 個 group 中的其中一個。group[i] 代表第 i 個 item 所屬的 group, 如果第 i 個 item 不屬於任何 group, 則 group[i] = -1。item 和 group 都從 0 開始編號的。可能存在 group 不負責任何 item。

返回 sorted list 滿足:

  • 同一 group 的 item 排序後應彼此相鄰
  • item 之間存在一定的依賴關係 beforeItems, 其中 beforeItems[i] 代表進行第 i 個 item 前應完成的所有 item

如果存在多個解, 返回其中一個即可。若沒有解, 則返回 empty list。

注意：beforeItems[i] 沒有重複的元素。

Solution：

想法：利用 Topological Sort + BFS, 首先我們需要找出同一 group 內的 item 順序, 然後再找出不同 group 之間的順序, 最後遍歷 group 順序和 group 內的 item 順序即可。需要注意的是, group[i] == -1 的 items 並不屬於同一個 group, 不必滿足相鄰條件, 因此我們要對那些 group[i] == -1 的 items 重新編號, 讓他們每個都擁有一個屬於自己的 group id

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        // 對 group 進行前處理 : 賦予 groupId == -1 的 item 一個屬於自己的 new group id
        int newGroupId = m;
        for (int i = 0; i < n; ++i) {
            if (group[i] == -1) {
                group[i] = newGroupId++;
            }
            groupItems[group[i]].emplace(i); // 紀錄每個 group 所擁有的 item
        }

        // 建立同一個 group 內的 graph
        for (int i = 0; i < n; ++i) {
            // j -> i (j 指向 i)
            for (int& j : beforeItems[i]) {
                // 不同 group 跳過
                if (group[i] != group[j]) {
                    continue;
                }

                // 題目保證 beforeItems[i] 沒有重複元素
                adj[j].emplace(i);
                ++inDegree[i];
            }
        }

        // 對同一 group 內的 item 進行 sorting
        unordered_map<int, vector<int>> groupItemOrder;
        for (const auto& [groupId, items] : groupItems) {
            groupItemOrder[groupId] = topologySort(items);

            // group 內的 item 順序無解
            if (groupItemOrder[groupId].size() != items.size()) {
                return {};
            }
        }

        // 建立不同 group 之間的 graph
        adj.clear();
        inDegree.clear();
        for (int i = 0; i < n; ++i) {
            // group[j] -> group[i] (group[j] 指向 group[i])
            for (const auto& j : beforeItems[i]) {
                // 同一 group 跳過
                if (group[i] == group[j]) {
                    continue;
                }

                // group 之間有可能會有重複
                // e.g. 同一 group 內的 node 同時指向另外一個 group 的 node
                if (adj[group[j]].find(group[i]) == adj[group[j]].end()) {
                    adj[group[j]].emplace(group[i]);
                    ++inDegree[group[i]];
                }
            }
        }

        // 得到所有 group
        unordered_set<int> groups;
        for (int i = 0; i < n; ++i) {
            groups.emplace(group[i]);
        }

        // 對不同 group 進行排序
        vector<int> groupOrder = topologySort(groups);
        vector<int> res;
        for (const auto& groupId : groupOrder) {
            for (const auto& item : groupItemOrder[groupId]) {
                res.emplace_back(item);
            }
        }

        return res;
    }

private:
    unordered_map<int, int> inDegree;
    unordered_map<int, unordered_set<int>> adj; // adjacency list
    unordered_map<int, unordered_set<int>> groupItems; // 紀錄每個 group 所有的 item

    vector<int> topologySort(unordered_set<int>& nodes){
        queue<int> q;
        for (const auto& node : nodes) {
            if (inDegree[node] == 0) {
                q.emplace(node);
            }
        }

        vector<int> res;
        while (!q.empty()) {
            const auto cur = q.front();
            q.pop();
            res.emplace_back(cur);

            for (const auto& v : adj[cur]) {
                if (--inDegree[v] == 0) {
                    q.emplace(v);
                }
            }
        }

        // size 不同代表有 cycle, 無解
        return (res.size() != nodes.size()) ? vector<int>() : res;
    }
};
  • time：$O(m + n^2 + E_{group} + E_{item})$ ➔ $E_{group}$、$E_{item}$ 代表 group、item 在 graph 中的 edge
    • $O(m)$：對 group 進行前處理
    • $O(n)$ ：建立 item 的 inDegree
    • $O(n^2)$：建構 item 的 adjacency list。worse case：第 1 個頂點指向所有剩餘 n − 1 個頂點，第 2 個頂點指向所有剩餘 n - 2 個頂點, 依此類推…
    • $O(n + E_{item})$：$O(V + E)$, 對 item 進行 topological sort
    • $O(m)$：建構 group 的 adjacency list、建立 group 的 inDegree
    • $O(m + E_{group})$：$O(V + E)$, 對 group 進行 topological sort
    • $O(m + n)$：得到 res
  • space：$O(m + n^2)$
    • $O(m)$：group 的 adjacency lis
    • $O(n^2)$：item 的 adjacency list
    • $O(m)$：group 的 inDegree
    • $O(n)$：item 的 inDegree