今天看了下leetcode周赛的题目,没怎么做,第四题是一道Hard题目,看了下题意感觉要用拓扑排序,但是这道题除了依赖关系,还有一个分组的变量,导致这道题处理起来会复杂些,可能需要2次拓扑排序或者1次复杂的拓扑排序。
下午看了下排名第一的题解,果然是2次拓扑排序,代码比较精简,值得学习一下。
来看下本次比赛这道题的通过次数
,这次是真的很低。
来看题:
公司共有 n 个项目和 m 个小组,每个项目要不没有归属,要不就由其中的一个小组负责。
我们用 group[i] 代表第 i 个项目所属的小组,如果这个项目目前无人接手,那么 group[i] 就等于 -1。(项目和小组都是从零开始编号的)
请你帮忙按要求安排这些项目的进度,并返回排序后的项目列表:
同一小组的项目,排序后在列表中彼此相邻。 项目之间存在一定的依赖关系,我们用一个列表 beforeItems 来表示,其中 beforeItems[i] 表示在进行第 i 个项目前(位于第 i 个项目左侧)应该完成的所有项目。 结果要求:
如果存在多个解决方案,只需要返回其中任意一个即可。
如果没有合适的解决方案,就请返回一个 空列表。
输入: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]
输入:n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]] 输出:[] 解释:与示例 1 大致相同,但是在排序后的列表中,4 必须放在 6 的前面。
大概思路:
1、首先对于所有的项目,将他们之间的依赖关系连成边,然后进行拓扑排序,解决掉同一个组内元素先后的问题。
2、排序后,进行分组,按组的依赖关系连成边,然后进行拓扑排序,解决掉多个组的先后问题。
3、这时候可以将排序后的组合并起来,返回即可。
源代码:
const int MAXN = 30010;
vector<int> v[MAXN];
int deg[MAXN];
void clear(int n)
{
for (int i = 0; i < n; ++i)
{
v[i].clear();
deg[i] = 0;
}
}
void addedge(int x, int y)
{
v[x].push_back(y);
deg[y] ++;
}
int head, tail, Q[MAXN];
bool topsort(int n)
{
head = 1;
tail = 0;
for (int i = 0; i < n; ++i)
if (!deg[i])
{
Q[++tail] = i;
}
while (head <= tail)
{
int x = Q[head++];
for (auto y : v[x])
if (!--deg[y]) Q[++tail] = y;
}
return tail == n;
}
class Solution {
public:
vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
clear(n);
for (int i = 0; i < n; ++i)
{
for (auto x : beforeItems[i])
{
//元素间的依赖关系
addedge(x, i);
}
}
//top排序进行分组
if (!topsort(n)) return {};
int tmp_m = m;
for (int i = 0; i < n; ++i)
{
if (group[i] == -1)
{
group[i] = m++;
}
}
vector<vector<int>> v(m);
for (int i = 1; i <= n; ++i)
v[group[Q[i]]].push_back(Q[i]);
clear(m);
for (int i = 0; i < n; ++i)
{
for (auto x : beforeItems[i])
{
if (group[x] == group[i]) continue;
//组之间的依赖关系
addedge(group[x], group[i]);
}
}
//对组进行top排序
if (!topsort(m)) return {};
vector<int> ret;
//分组输出
for (int i = 1; i <= m; ++i)
{
for (auto x : v[Q[i]]) ret.push_back(x);
}
return ret;
}
};
再来回顾一下拓扑排序:
有n个任务,用1-n进行表示,任务可能存在依赖关系,(u,v)表示v需要依赖任务u,输出完成所有任务的序列。
拓扑排序就是解决这种存在先后关系的问题的算法。在上面的问题中,可以把每个任务看成图上的一个节点,对于(u, v)表示 u→v。
比如有3个任务,表示为1,2,3,任务依赖关系为(2,3) (3,1) 那么就有如下图所示:
任务序列也就是2,3,1。对于有些图,序列可能是多个。
在图论中,由一个有向无环图DAG的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序
1 每个顶点出现且只出现一次; 2 若A在序列中排在B的前面,则在图中不存在从B到A的路径。
卡恩于1962年提出的算法。简单来说就是,假设L是存放结果的列表,先找到那些入度为零的节点,把这些节点放到L中,因为这些节点没有任何的父节点。然后把与这些节点相连的边从图中去掉,再寻找图中的入度为零的节点。对于新找到的这些入度为零的节点来说,他们的父节点已经都在L中了,所以也可以放入L。重复上述操作,直到找不到入度为零的节点。如果此时L中的元素个数和节点总数相同,说明排序完成;如果L中的元素个数和节点总数不同,说明原图中存在环,无法进行拓扑排序。
伪代码
bool toposort() {
q = new queue();
for (i = 0; i < n; i++)
if (in_deg[i] == 0) q.push(i);
ans = new vector();
while (!q.empty()) {
u = q.pop();
ans.push_back(u);
for each edge(u, v) {
if (--in_deg[v] == 0) q.push(v);
}
}
if (ans.size() == n) {
for (i = 0; i < n; i++)
std::cout << ans[i] << std::endl;
return true;
} else {
return false;
}
}
简单的理解,遍历每个节点N,从N开始进行DFS搜索,如果能够完成搜索,则说明存在拓扑排序。如下代码。
// dfs 版本
bool dfs(int u) {
c[u] = -1;
for (int v = 0; v <= n; v++)
if (G[u][v]) {
if (c[v] < 0)
return false;
else if (!c[v])
dfs(v);
}
c[u] = 1;
topo.push_back(u);
return true;
}
bool toposort() {
topo.clear();
memset(c, 0, sizeof(c));
for (int u = 0; u <= n; u++)
if (!c[u])
if (!dfs(u)) return false;
reverse(topo.begin(), topo.end());
return true;
}