图论：1203. 项目管理（以小组为单位进行拓扑排序）

文章目录

1.问题分析
2.思路整理
3.官解思路

LeetCode：1203. 项目管理
在这里插入图片描述

建议直接看思路整理

1.问题分析

仔细读题可以发现，如果不考虑小组项目彼此相邻，则项目之间的依赖关系就是一个拓扑排序。

但是如果要考虑小组项目彼此相邻，问题就复杂起来了。

容易想到两种策略，第一种就是前期处理，处理拓扑图使得小组也成为一个约束条件，保证一个小组一个小组输出拓扑序；第二种是后期处理，先求出拓扑序然后按小组进行分类，然后再判断该拓扑序是否合法（该方法复杂度过高）。

我们来看第一种策略，很容易想到将小组也作为一个顶点，其后继是所有它管理的项目，这样轮到该小组，该小组的项目才能进行。而然要使得按一个小组一个小组来，那么前一个小组在输出拓扑序未输出完时，后一个小组不能输出，相当于前一个小组制约了后一个小组。这样的话怎么做呢？

我们知道仅仅加一个小组是不行的，因为其入度为0，导致顺序又是乱的，那我们是否可以用前面一个小组的每个项目都连接到后一个小组，这样的话前面的小组的每一个项目完成了才能进行后面的小组，后面这个小组才能开放自己的项目。如果有多个小组可以进行，那么它们一定互不影响，因为根据前面的约束条件，已经没有其他小组的项目可以约束它，我们将其依次放入一个栈中，以便于之后一个一个开放。并且只能在没有可进行的时候开放，原因在于，可能有的没有小组约束，它们进行完成之后，再考虑小组的，不然也会产生顺序问题。

考虑了这个问题后，一个小组的前驱已经被解决了，但是小组的后继呢？这你可能会觉得有点矛盾，但并不是这样，小组的约束解决了。但是没有小组的项目也是需要约束的，因为它相当于自己作为自己的小组。

实现如下：时间复杂度： $O (n + m)$
在这里插入图片描述

class Solution {
public:vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {vector<int> result;//存储最终结果stack<int> sta; // 存储可开放的小组queue<int> q;//预处理，将小组进行约束vector<vector<int>> edges(n + m); //edges[i]表示其后继vector<int> inDegrees(n + m, 0);//入度表示约束条件，小组的编号增加偏移m//求入度 并构造 边集for(int i = 0; i < beforeItems.size(); ++ i){vector<int> & pre = beforeItems[i];//pre 是 i的前驱，pre的小组也必然是i小组的前驱（除非相同）for(auto & p : pre){edges[p].emplace_back(i);inDegrees[i] ++;if(group[i] != - 1 && group[p] != group[i]){//任何对项目的约束，也都转化成小组之间的约束if(group[p] != -1){edges[group[p] + n].emplace_back(group[i] + n);inDegrees[group[i] + n] ++;}}}}//建立小组对项目的约束for(int i = 0; i < group.size(); ++ i){if(group[i] != -1){edges[group[i] + n].emplace_back(i);inDegrees[i] ++;}}//求入度为0for(int i = 0; i < inDegrees.size(); ++ i){if(inDegrees[i] == 0){if(i < n)q.push(i);else sta.push(i);}}//构建组内成员对后继项目的共同约束unordered_set<int> st;for(int i = 0; i < beforeItems.size(); ++ i){for(auto & pre : beforeItems[i]){if(group[i] == -1 && group[pre] != -1 && st.count(group[pre]) == 0){st.insert(group[pre]);for(auto & v : edges[group[pre] + n]){edges[v].emplace_back(i);inDegrees[i] ++;}}}}while(!sta.empty() || !q.empty()){if(q.empty()){//只能开放小组了q.push(sta.top()); sta.pop();}while(!q.empty()){int u = q.front();q.pop();if(u < n) result.emplace_back(u);for(auto & v : edges[u]){inDegrees[v] --;if(inDegrees[v] == 0){if(v < n) {q.push(v);}else sta.push(v);}}}}if(result.size() != n) return vector<int>{};return result;}
};

如果将单个项目也当成小组，我们可以进一步优化，对于可以执行的单个项目，约束它的所有项目都已经执行完毕，我们在任何时候执行都可以，由于它也当做小组，为了避免它和可以执行的其他小组冲突，我们将其也入栈，直到无可奈何才执行它。这样就不用创建对于它的约束了。
在这里插入图片描述

class Solution {
public:vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {vector<int> result;//存储最终结果stack<int> sta; // 存储可开放的小组queue<int> q;//预处理，将小组进行约束vector<vector<int>> edges(n + m); //edges[i]表示其后继vector<int> inDegrees(n + m, 0);//入度表示约束条件，小组的编号增加偏移m//求入度 并构造 边集for(int i = 0; i < beforeItems.size(); ++ i){vector<int> & pre = beforeItems[i];//pre 是 i的前驱，pre的小组也必然是i小组的前驱（除非相同）for(auto & p : pre){edges[p].emplace_back(i);inDegrees[i] ++;if(group[i] != - 1 && group[p] != group[i]){//任何对项目的约束，也都转化成对小组的约束edges[p].emplace_back(group[i] + n);inDegrees[group[i] + n] ++;}}}//建立小组对项目的约束for(int i = 0; i < group.size(); ++ i){if(group[i] != -1){edges[group[i] + n].emplace_back(i);inDegrees[i] ++;}}//求入度为0for(int i = 0; i < inDegrees.size(); ++ i){if(inDegrees[i] == 0){if(i < n)q.push(i);else sta.push(i);}}while(!sta.empty() || !q.empty()){if(q.empty()){//只能开放小组了q.push(sta.top()); sta.pop();}while(!q.empty()){int u = q.front();q.pop();if(u < n) result.emplace_back(u);for(auto & v : edges[u]){inDegrees[v] --;if(inDegrees[v] == 0){if(v < n && group[v] != -1) {q.push(v);}else sta.push(v);}}}}if(result.size() != n) return vector<int>{};return result;}
};

2.思路整理

这样一个困难题被思考出来感觉非常的不可思议。

思路的主要内容是：

给小组增加编号，小组也当做图中的顶点，小组可以执行了，整个小组项目才可以执行，这样保证了小组项目的约束一致性。
小组之间存在约束条件，并且对于两个项目 $(u, v)$ 而言，它们的小组也存在约束即 $u$ 的小组要先于 $v$ 的小组项目执行。
- 如果不对小组进行约束的话，小组入度为0，小组的增加形同虚设
- 我们找到了两个项目 $(u, v)$ 的约束关系，同时找到了小组的约束关系，前一个小组进行之后，后一个小组才能进行。
我们对小组延迟进行执行，将其单独放入一个栈中，只有拓扑排序时队列中没有可执行项目时，才从栈中取出一个小组进行执行，这样保证了是一个一个小组进行的，并且这个小组的顺序是满足小组之间的约束条件的。
对于无小组的项目，我们当做是一个项目的小组即可，并且我们只需要在其能运行时将其入栈保证其不影响当前组的项目顺序即可，这样它执行时，一定是其他小组完成时，而不会插在其他小组中间执行。

总体来看，这个思路和官解思路没啥区别，实际上也是以小组为单位进行拓扑排序的一种方式。只不过我是增加一个数据结构栈 和增加小组之间约束条件来保证这一点的。

小组之间的约束条件，加上栈保证正在执行的小组必须完整的执行完，保证了以小组为单位进行拓扑排序。

        //求入度 并构造 边集for(int i = 0; i < beforeItems.size(); ++ i){vector<int> & pre = beforeItems[i];//pre 是 i的前驱，pre的小组也必然是i小组的前驱（除非相同）for(auto & p : pre){edges[p].emplace_back(i);inDegrees[i] ++;if(group[i] != - 1 && group[p] != group[i]){//任何对项目的约束，也都转化成小组之间的约束if(group[p] != -1){edges[group[p] + n].emplace_back(group[i] + n);inDegrees[group[i] + n] ++;}}}}