前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >UVA10305 | 拓扑排序

UVA10305 | 拓扑排序

作者头像
ACM算法日常
发布2018-08-07 16:56:42
3400
发布2018-08-07 16:56:42
举报
文章被收录于专栏:ACM算法日常

John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is only possible if other tasks have already been executed.

John有n件工作要做,不幸的是这些工作并不独立,而是某件工作需要在另一件已经执行完了以后才能执行。

Input The input will consist of several instances of the problem. Each instance begins with a line containing two integers, 1 ≤ n ≤ 100 and m. n is the number of tasks (numbered from 1 to n) and m is the number of direct precedence relations between tasks. After this, there will be m lines with two integers i and j, representing the fact that task i must be executed before task j. An instance with n = m = 0 will finish the input.

输入会包括若干组。每组先输入 n([1,100])和 m,其中 n 代表标号为 1~n 的 n 件工作。接下来的 m 行给出工作之间的优先度,每行给出两个整数 i、j,代表 i 会在 j 之前执行,n = m = 0时结束输入。

Output For each instance, print a line with n integers representing the tasks in a possible order of execution.

对于每组数据,打印n个整数,代表着一种可能出现的执行顺序(意即多解输出某一解即可)。

Sample Input 5 4

1 2

2 3

1 3

1 5

0 0

Sample Output 1 4 2 5 3

介绍:

把每个变量看成一个点,“小于”关系看成有向边(比如输入1 2,我们可以画箭头1-->2),这样就可以把数据转化为一个有向图。把图的所有结点排序使得每一条有向边(u,v)对应的u都排在v的前边(不一定相邻)。在图论中,这个问题称为拓扑排序。

本题思路:

显然,我们无法从前到后去贪心选取路径,比如用样例来讲,如果我们先搜索到了 1->3 这条路,然后就储存在结果上的话,无法得知是否还有 1->2->3 这个限定路径,之后再搜到 2 这个点也没法往里补,而 5 这个点处在哪里也不好写命令。

所以反过来贪心:可以发现当深搜到最底端到达点 3 时,它后面再也没有点了,那么无论如何处置其他的点,3放在最后总是没错的。而为了得出点 1 和点 2 的顺序,可以在某个点for遍历了它的全部出度并深搜以后,再将此点放入拓扑序的前端。比如点 1 先扫描到了点 3,到头了,3放里;然后点 1 还有个指向点 2 的箭头,再dfs点 2,于是点 2 也放里了;然后点 1 遍历结束,点 1 放里……请用代码细细体会。

代码语言:javascript
复制
 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6using namespace std;
 7
 8const int maxn = 105;
 9int n, m;
10int topo[maxn], temp;//最终的拓扑序
11bool book[maxn];//记录是否已经访问过某点
12vector <int> chu[maxn];//chu[i]储存i指向的所有点
13
14void dfs(int cur)
15{
16    for (int i : chu[cur])
17    //C++11的特性,表示遍历了vector(实际上哪个容器都可以这么用),i代表具体元素值而不是位置
18        if (!book[i])   dfs(i);
19    book[cur] = true;
20    topo[temp--] = cur;
21}
22
23int main()
24{
25    while (~scanf("%d%d", &n, &m) && (n | m))//注意m是可以等于0的,n、m同时等于0才终止
26    {
27        //输入和预处理
28        for (int i = 0; i < m; i++)
29        {
30            int a, b;
31            scanf("%d%d", &a, &b);
32            chu[a].push_back(b);//把b作为a的出度
33        }
34        //深搜
35        memset(book, false, sizeof(book));
36        temp = n;
37        for (int i = 1; i <= n; i++)
38            if (!book[i])   dfs(i);
39        //输出
40        for (int i = 1; i <= n; i++)
41            chu[i].clear(), printf("%d%c", topo[i], " \n"[i==n]);
42    }
43}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-07-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档