UVA10305 | 拓扑排序

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 放里……请用代码细细体会。

 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}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-07-29

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏做全栈攻城狮

电脑小白自学软件编程-.Net语法基础之循环语句,纯技巧干货

课程总目录:因头条无法自定义目录,大家关注:“做全栈攻城狮”微信公众号。回复“.net目录”,即可获取。微信公众号也包含大量学习教程,等你来~

1123
来自专栏恰同学骚年

.NET中那些所谓的新语法之一:自动属性、隐式类型、命名参数与自动初始化器

开篇:在日常的.NET开发学习中,我们往往会接触到一些较新的语法,它们相对以前的老语法相比,做了很多的改进,简化了很多繁杂的代码格式,也大大减少了我们这些菜鸟码...

752
来自专栏黑泽君的专栏

java基础学习_IO流03_字符流、IO流小结、案例_day21总结

812
来自专栏小樱的经验随笔

Uva 11729 Commando War (简单贪心)

Uva 11729  Commando War (简单贪心) There is a war and it doesn't look very promising...

2666
来自专栏智能大石头

深度解析C++拷贝构造函数

自2003年开始,断断续续用了12年C++,直到这两年做物联网嵌入式开发,感觉对C++的掌握仅有10%左右。 习惯了C#开发,C++倒显得难以下手!今天就一个函...

2059
来自专栏chafezhou

fire让命令行接口更简单

1245
来自专栏好好学java的技术栈

一文看透java8新特性

毫无疑问,Java 8发行版是自Java 5(发行于2004,已经过了相当一段时间了)以来最具革命性的版本。Java 8 为Java语言、编译器、类库、开发工具...

1132
来自专栏happyJared

设计模式入门:原型模式

  实际应用中,原型模式可以简单理解为克隆操作。在大多数面向对象编程语言中,实现克隆操作并不复杂,对于Java,我们只需继承Cloneable接口,并重写Obj...

642
来自专栏Echo is learning

字符、字符集、编码,以及它们python中会遇到的一些问题(上)

1907
来自专栏学习力

《Java从入门到放弃》框架入门篇:Struts2的基本数据传递方式 推荐

1624

扫码关注云+社区