首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐
2025年7月19日 星期六 9:48pm

【拓扑排序】【 图论】1203. 项目管理

  • 25-02-22 05:20
  • 2246
  • 6511
blog.csdn.net

本文涉及知识点

拓扑排序 图论

LeetCode1203. 项目管理

有 n 个项目,每个项目或者不属于任何小组,或者属于 m 个小组之一。group[i] 表示第 i 个项目所属的小组,如果第 i 个项目不属于任何小组,则 group[i] 等于 -1。项目和小组都是从零开始编号的。可能存在小组不负责任何项目,即没有任何项目属于这个小组。
请你帮忙按要求安排这些项目的进度,并返回排序后的项目列表:
同一小组的项目,排序后在列表中彼此相邻。
项目之间存在一定的依赖关系,我们用一个列表 beforeItems 来表示,其中 beforeItems[i] 表示在进行第 i 个项目前(位于第 i 个项目左侧)应该完成的所有项目。
如果存在多个解决方案,只需要返回其中任意一个即可。如果没有合适的解决方案,就请返回一个 空列表 。
示例 1:
输入: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] 不含重复元素

拓扑排序

同一小组的项目,排序后在列表中彼此相邻。 → \rightarrow → A小组的某项目依赖B小组的某项目,则B小组全部完成后,才能处理A小组的项目。
最容易想到的办法,先对项目组拓扑排序,再对组内项目拓扑排序。这样内存超了。时间也很可能超。错误代码如下:

class CTopSort
{
public:
void Init(const vector& vNeiBo)
{
m_c = vNeiBo.size();
m_vBackNeiBo.resize(m_c);
vector vOutDeg(m_c);
for (int cur = 0; cur < m_c; cur++)
{
vOutDeg[cur] = vNeiBo[cur].size();
for (const auto& next : vNeiBo[cur])
{
m_vBackNeiBo[next].emplace_back(cur);
}
}
queue que;
for (int i = 0; i < m_c; i++)
{
if (0 == vOutDeg[i])
{
que.emplace(i);
m_vLeaf.emplace_back(i);
OnDo(-1, i);
}
}
while (que.size())
{
const int cur = que.front();
que.pop();
for (const auto& next : m_vBackNeiBo[cur])
{
vOutDeg[next]–;
if (0 == vOutDeg[next])
{
que.emplace(next);
OnDo(cur, next);
}
}
};
}
int m_c;
vector m_vLeaf;
protected:
virtual void OnDo(int pre, int cur) = 0;
vector m_vBackNeiBo;
};

class CMyTopSort : public CTopSort
{
public:
vector m_vTopSort;
protected:
virtual void OnDo(int pre, int cur) override
{
m_vTopSort.emplace_back(cur);
}
};
class Solution {
public:
vector sortItems(int n, int m, vector& group, vector& beforeItems) {
int iMaxGroup = *std::max_element(group.begin(), group.end());
for (auto& n : group)
{
if (-1 == n)
{
n = ++iMaxGroup;
}
}
vector vNeiBo(1 + iMaxGroup);
vector> vItemNeiBo(1 + iMaxGroup, vector(n));
for (int i = 0; i < beforeItems.size(); i++)
{
for (const auto& bef : beforeItems[i])
{
if (group[i] != group[bef]) {
vNeiBo[group[i]].emplace_back(group[bef]);
}
else {
vItemNeiBo[group[i]][i].emplace_back(bef);
}
}
}
for (auto& v : vNeiBo)
{
unordered_set tmp(v.begin(), v.end());
vector(tmp.begin(), tmp.end()).swap(v);
}
CMyTopSort top;
top.Init(vNeiBo);
vector vNodeOfGroup(iMaxGroup + 1);
for (int i = 0; i < group.size(); i++)
{
vNodeOfGroup[group[i]].emplace_back(i);
}
vector vRet;
for (const auto& iGroup : top.m_vTopSort)
{
CMyTopSort topItem;
topItem.Init(vItemNeiBo[iGroup]);
for (const auto& n : topItem.m_vTopSort)
{
if (group[n] == iGroup)
{
vRet.emplace_back(n);
}
}
}
return (vRet.size() == group.size()) ? vRet : vector{};
}
};

改进方法

一,修改拓扑排序封装类,使得支持哈希映射,这样可以处理非连续节点。
二,修改拓扑封装类,项目和项目组出度同时为0,才进行拓扑排序。
有一个简单的方法,不用修改拓扑类。
每个项目组增加两个虚拟节点,组前节点,组内所有项目都依赖它;组后节点,它依赖所有组内项目。
A组依赖B组,则A组的组前节点A1,依赖B组的组后节点B2。
下图展示了A组包括两个节点{0,1},B组也包括两个节点{2,3}。
在这里插入图片描述
2,3 处理完才会处理B2,B2处理完,才会处理A1。A1处理完才会处理0和1。

细节很多

组号为-1的项目要重复分配新的组号,避免把-1的项目看成同一项目组。
邻接点不能有重复节点。
这样并不能保证同一个项目组挨在一起。
m_vNodeOfGroup 记录各项目组的拓扑序。m_vGroupNo记录拓扑序各节点的项目组号。按m_vGroupNo的顺序将结果复制到vRet。m_vGroupNo可以用哈希集合去重,也可以复制完就删除。

代码

class CTopSort
{
public:	
	void Init(const vector<vector<int>>& vNeiBo)
	{
		m_c = vNeiBo.size();
		m_vBackNeiBo.resize(m_c);
		vector<int> vOutDeg(m_c);
		for (int cur = 0; cur < m_c; cur++)
		{
			vOutDeg[cur] = vNeiBo[cur].size();	
			for (const auto& next : vNeiBo[cur])
			{
				m_vBackNeiBo[next].emplace_back(cur);
			}
		}
		queue<int> que;
		for (int i = 0; i < m_c; i++)
		{
			if (0 == vOutDeg[i])
			{
				que.emplace(i);
				m_vLeaf.emplace_back(i);
				OnDo(-1, i);
			}
		}

		while (que.size())
		{
			const int cur = que.front();
			que.pop();
			for (const auto& next : m_vBackNeiBo[cur])
			{
				vOutDeg[next]--;
				if (0 == vOutDeg[next])
				{
					que.emplace(next);
					OnDo(cur, next);
				}
			}
		};
	}
	int m_c;
	vector<int> m_vLeaf;
protected:
	virtual void OnDo(int pre, int cur) = 0;
	vector<vector<int>> m_vBackNeiBo;
};

class CMyTopSort : public CTopSort
{
public:
	CMyTopSort(const vector<int>& vNodeToGroup,int iGroupCount):m_vNodeToGroup(vNodeToGroup)
	{
		m_vNodeOfGroup.resize(iGroupCount);
	}
	vector<vector<int>> m_vNodeOfGroup;
	vector<int> m_vGroupNo;
protected:
	virtual void OnDo(int pre, int cur) override
	{
		if (cur < m_vNodeToGroup.size())
		{
			const int iGroup = m_vNodeToGroup[cur];
			m_vNodeOfGroup[iGroup].emplace_back(cur);
			m_vGroupNo.emplace_back(iGroup);
		}		
	}
	const vector<int>& m_vNodeToGroup;
};
class Solution {
public:
	vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
		int iMaxGroup = *std::max_element(group.begin(), group.end());
		for (auto& tmp : group)
		{
			if (-1 == tmp)
			{
				tmp = ++iMaxGroup;
			}
		}
		vector<vector<int>> vNodeOfGroup(iMaxGroup + 1);
		for (int i = 0; i < group.size(); i++)
		{
			vNodeOfGroup[group[i]].emplace_back(i);
		}
		vector<vector<int>> vNeiBo((1 + iMaxGroup)*2+n );
		for (int i = 0; i < vNodeOfGroup.size(); i++)
		{
			for (const auto& tmp : vNodeOfGroup[i])
			{
				vNeiBo[tmp].emplace_back(n + 2 * i);//组内所有节点都依赖组前节点
				vNeiBo[n + 2 * i + 1].emplace_back(tmp);//组后节点依赖所有组内节点
			}
		}	
		for (int i = 0; i < beforeItems.size(); i++)
		{
			for (const auto& bef : beforeItems[i])
			{
				if (group[i] == group[bef]) {
					vNeiBo[i].emplace_back(bef);
				}	
				else {
					vNeiBo[n + 2 * group[i]].emplace_back(n + 2 * group[bef] + 1);
				}
			}
		}
		for (auto& v : vNeiBo)
		{//删除重复节点
			unordered_set<int> tmp(v.begin(), v.end());
			vector<int>(tmp.begin(), tmp.end()).swap(v);
		}		
		CMyTopSort top(group,iMaxGroup+1);
		top.Init(vNeiBo);		
		vector<int> vRet;
		for (const auto& tmp : top.m_vGroupNo)
		{
			auto& v = top.m_vNodeOfGroup[tmp];
			vRet.insert(vRet.end(), v.begin(), v.end());
			v.clear();
		}
		return (vRet.size() == group.size()) ? vRet : vector<int>{};
	}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124

测试用例

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	int n,  m;
	vector<int> group;
	vector<vector<int>> beforeItems;
	{
		Solution sln;
		n = 8, m = 2, group = { -1,-1,1,0,0,1,0,-1 }, beforeItems = { {},{6},{5},{6},{3},{},{4},{} };
		auto res = sln.sortItems(n, m, group, beforeItems);
		Assert({ }, res);
	}
	{
		Solution sln;
		n = 8, m = 2, group = { -1,-1,1,0,0,1,0,-1 }, beforeItems = { {},{6},{5},{6},{3,6},{},{},{} };
		auto res = sln.sortItems(n, m, group, beforeItems);
	//	Assert({ 6,3,4,1,5,2,0,7 }, res);
	}	
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40

2023年4月

class Solution {
public:
vector sortItems(int n, int m, vector& group, vector& beforeItems) {
//没有分组的分配一个新组号
m_vGroupItems.resize(m );
for (int j = 0; j < n;j++ )
{
auto& g = group[j];
if (-1 == g)
{
g = m_vGroupItems.size();
m_vGroupItems.emplace_back();
}
m_vGroupItems[g].emplace_back(j);
}
const int GroupNum = m_vGroupItems.size();
vector vGroupBefore(GroupNum), vGroupAfter(GroupNum);
for (int j = 0; j < n; j++)
{
const auto& v = beforeItems[j];
for (const auto& before : v)
{
const int iGroup = group[j];
const int iBeforeGroup = group[before];
if (iGroup == iBeforeGroup)
{
continue;
}
vGroupBefore[iGroup].emplace(iBeforeGroup);
vGroupAfter[iBeforeGroup].emplace(iGroup);
}
}
auto vGroups = Order(vGroupBefore, vGroupAfter);
if (vGroups.size() != m_vGroupItems.size())
{
return vector();
}
vector vRet;
for (const auto& iCurGroup : vGroups)
{
const auto& vItemsCurGroup = m_vGroupItems[iCurGroup];
const int iCurGroupItemSize = vItemsCurGroup.size();
std::unordered_map mIndexToGroupIndex;
for (const int& item : vItemsCurGroup)
{
mIndexToGroupIndex[item] = mIndexToGroupIndex.size();
}
vector vItemBefore(iCurGroupItemSize), vItemAfter(iCurGroupItemSize);
for (const int& item : vItemsCurGroup)
{
const int iCurItemIndex = mIndexToGroupIndex[item];
for (const int& before : beforeItems[item])
{
if (group[before] != iCurGroup)
{
continue;
}
const int iBeforeIndex = mIndexToGroupIndex[before];
vItemBefore[iCurItemIndex].emplace(iBeforeIndex);
vItemAfter[iBeforeIndex].emplace(iCurItemIndex);
}
}
vector vCurGroupItemOrder = Order(vItemBefore,vItemAfter);
if (iCurGroupItemSize != vCurGroupItemOrder.size())
{
return vector();
}
for (const int iCurGroupItem : vCurGroupItemOrder)
{
vRet.emplace_back(vItemsCurGroup[iCurGroupItem]);
}
//std::copy(vGroupItems[g].begin(), vGroupItems[g].end(), std::back_inserter(vRet));
}

	return vRet;
}
vector Order(vector>& vBefore, vector>& vAfter)
{	
	vector vOrders;
	for (int j = 0; j < vBefore.size(); j++)
	{
		if (vBefore[j].size() == 0)
		{
			vOrders.emplace_back(j);
		}
	}

	int hasDo = 0;
	while (hasDo < vOrders.size())
	{
		const auto cur = vOrders[hasDo];
		hasDo++;
		for (auto& after : vAfter[cur])
		{
			vBefore[after].erase(cur);
			if (vBefore[after].empty())
			{
				vOrders.emplace_back(after);
			}
		}
		vAfter[cur].clear();
	}
	return vOrders;
}
vector> m_vGroupItems;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览60496 人正在系统学习中
群中有博文配套源码
QQ群名片
注:本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/136904872"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

101
推荐
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top