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
题目类型：拓扑排序
算法分析：按照基本算法直接计算输出即可，下面第一个是基于队列的BFS实现，第二个是基于栈的DFS实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
/************************************************** filename :h.cpp author :maksyuki created time :2018/6/1 0:11:38 last modified :2018/6/1 0:19:13 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 166; int n, m; int in[maxn]; vector<int> g[maxn]; void init() { memset(in, 0, sizeof(in)); for(int i = 0; i < maxn; i++) g[i].clear(); } int main() { #ifdef LOCAL CFF; //CFO; #endif while(cin >> n >> m) { if(!n && !m) break; init(); int va, vb; for(int i = 1; i <= m; i++) { cin >> va >> vb; in[vb]++; g[va].emplace_back(vb); } queue<int> qu; for(int i = 1; i <= n; i++) if(!in[i]) qu.push(i); bool is_first = true; while(!qu.empty()) { int tt = qu.front(); qu.pop(); if(is_first) { is_first = false; cout << tt; } else cout << " " << tt; int glen = g[tt].size(); for(int i = 0; i < glen; i++) { in[g[tt][i]]--; if(!in[g[tt][i]]) qu.push(g[tt][i]); } } cout << endl; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
/************************************************** filename :i.cpp author :maksyuki created time :2018/6/1 0:46:45 last modified :2018/6/1 0:59:47 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 166; int n, m; vector<int> g[maxn]; stack<int> ans; bool vis[maxn]; void init() { memset(vis, false, sizeof(vis)); while(!ans.empty()) ans.pop(); for(int i = 0; i < maxn; i++) g[i].clear(); } void dfs(int u) { vis[u] = true; int len = g[u].size(); for(int i = 0; i < len; i++) { int v = g[u][i]; if(!vis[v]) dfs(v); } ans.push(u); } int main() { #ifdef LOCAL CFF; //CFO; #endif while(cin >> n >> m) { if(!n && !m) break; init(); int u, v; for(int i = 1; i <= m; i++) { cin >> u >> v; g[u].emplace_back(v); } for(int i = 1; i <= n; i++) if(!vis[i]) dfs(i); bool is_first = true; while(!ans.empty()) { if(is_first) { is_first = false; cout << ans.top(); } else cout << " " << ans.top(); ans.pop(); } cout << endl; } return 0; } |
- « 上一篇：uva816
- uva10129：下一篇 »