填寫問券˙抽7-11禮券工程師靠存股年領百萬股息法人:14檔今年本業虧定了黃國昌嗆周祝瑛 教室一...
2012-03-08 23:39:03 人氣(331) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA] 10305 - Ordering Tasks

0
收藏
0
推薦

Problem F

Ordering Tasks

Input: standard input

Output: standard output

Time Limit: 1 second

Memory Limit: 32 MB

 

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.

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.

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


拓樸排序


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define oo 100000
int map[101][101], indeg[101], outdeg[101];
int n, m, x, y, i;
void TopologicalSort() {
int i, j, degn;
for(i = 0; i < n; i++) {
for(j = 1; j <= n; j++) {
if(indeg[j] == 0)
break;
}
degn = j;
if(i) printf(" ");
printf("%d", degn);
indeg[degn] = -1;
for(j = 0; j < outdeg[degn]; j++)
indeg[map[degn][j]]--;
}
puts("");
}
int main() {
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0 && m == 0)
break;
memset(indeg, 0, sizeof(indeg));
memset(outdeg, 0, sizeof(outdeg));
for(i = 0; i < m; i++) {
scanf("%d %d", &x, &y);
map[x][outdeg[x]++] = y;
indeg[y]++;
}
TopologicalSort();
}
return 0;
}

10305Ordering Tasks
台長:Morris
人氣(331) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 838 - Worm World
此分類上一篇:[UVA] 10000 - Longest Paths

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文