专栏首页ACM算法日常leetcode 周赛155 | 项目管理之拓扑排序算法

leetcode 周赛155 | 项目管理之拓扑排序算法

今天看了下leetcode周赛的题目,没怎么做,第四题是一道Hard题目,看了下题意感觉要用拓扑排序,但是这道题除了依赖关系,还有一个分组的变量,导致这道题处理起来会复杂些,可能需要2次拓扑排序或者1次复杂的拓扑排序。

下午看了下排名第一的题解,果然是2次拓扑排序,代码比较精简,值得学习一下。

来看下本次比赛这道题的通过次数

,这次是真的很低。

来看题:

5200. 项目管理 显示英文描述

公司共有 n 个项目和 m 个小组,每个项目要不没有归属,要不就由其中的一个小组负责。

我们用 group[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、首先对于所有的项目,将他们之间的依赖关系连成边,然后进行拓扑排序,解决掉同一个组内元素先后的问题。

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)表示 uv

比如有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;
}

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:dansen

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces Round #549(div1)简析

    正解貌似有分四种情况什么的,我做时是发现各个起点其实都等价的,所以随便选一个起点,再暴举终点以暴举答案,更新即可。

    ACM算法日常
  • 水果Fruit(母函数) - HDU 2152

    转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

    ACM算法日常
  • #628 DIV2 题解

    组样例,每组给一个和个数 。将同一个序列重复次得到一个新序列,问可以从新序列中严格最长上升子序列长度为多少。

    ACM算法日常
  • 矩阵图的深度广度遍历

    图的常用表示方法就是矩阵和邻接表。 矩阵通常使用与规整的,且数据量较小的图,这种图直观上方便的表示出了图之间节点的相互关系。 图的数据结构 typedef st...

    用户1154259
  • Codeforces Round #549(div1)简析

    正解貌似有分四种情况什么的,我做时是发现各个起点其实都等价的,所以随便选一个起点,再暴举终点以暴举答案,更新即可。

    ACM算法日常
  • 八大经典排序算法总结

    终于到了排序部分了。这部分也是最难总结的,毕竟不同的排序算法思想多少会有差别,有些甚至完全不一样。今天不知道要码多少字。好吧,先为我的手指默哀三分钟~

    指点
  • BZOJ4872: [Shoi2017]分手是祝愿

    Description Zeit und Raum trennen dich und mich. 时空将你我分开。B 君在玩一个游戏,这个游戏由 n 个灯和 n...

    attack
  • 1436 孪生素数 2

    1436 孪生素数 2 时间限制: 2 s 空间限制: 1000 KB 题目等级 : 白银 Silver 题目描述 Description 如m=...

    attack
  • Codeforces Round #535 (Div. 3) E1. Array and Segments (Easy version)(思维+暴力)

    题目链接:http://codeforces.com/contest/1108/problem/E1

    Ch_Zaqdt
  • 并查集

    ​ 在我们需要判断某一些事物之间是否存在一定的关系的时候,我们最好的办法不是使用图而是使用并查集。因为我们关心的是他们之间是否有关系,而不是关心的他们到底...

    lwen

扫码关注云+社区

领取腾讯云代金券