# 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 ﬁnish the input.

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

Sample Input 5 4

1 2

2 3

1 3

1 5

0 0

Sample Output 1 4 2 5 3

``` 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}```

187 篇文章29 人订阅

0 条评论

## 相关文章

1123

752

812

### Uva 11729 Commando War （简单贪心）

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

2666

2059

1245

1132

### 设计模式入门：原型模式

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

642

1907

1624