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 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> using namespace std; struct typeNode{ int in; vector<int> from; vector<int> to; } node[505]; vector<int> req; vector<int> res; int main(){ int n = 0,m = 0; while (cin >> n >> m) { req.clear(); res.clear(); for (int i = 1; i <= n; i++) { node[i].to.clear(); node[i].from.clear(); node[i].in = 0; } for (int i = 1; i <= m; i++) { int a = 0,b = 0; cin >> b >> a; node[b].to.push_back(a); node[a].from.push_back(b); node[a].in++; } bool flag = true; while (flag) { flag = false; for (int i = 1; i <= n; i++) { if (node[i].in == 0) { res.push_back(i); node[i].in--; flag = true; for (int j = 0; j < node[i].to.size(); j++) { node[node[i].to[j]].in--; } break; } } } for (int i = 0; i < res.size();i++) { cout << res[i]; if (i != res.size()-1) { cout << " "; } } cout << endl; } return 0; } |
拓扑排序相关,还不怎么会,绕了好多弯路,要好好学习总结下嗯-_-#