AOJ 0519 Worst Sportswriter
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0519
解法
トポロジカルソートする。
途中で候補の頂点が複数あらわれた場合、順位表が複数ありえる。
O(V+E)だけど実装下手なせいでO(V^2)になった
#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 5000; vector<int> a[MAX_N]; int N, M; int b[MAX_N]; int main(){ scanf("%d %d", &N, &M); for(int i = 0; i < M; i++){ int p, q; scanf("%d %d", &p, &q); p--; q--; a[p].push_back(q); b[q]++; } bool f = false; vector<int> ans; for(int t = 0; t < N; t++){ for(int i = 0; i < N; i++){ if(b[i] == 0){ ans.push_back(i + 1); b[i] = -1; if(!f){ for(int j = i + 1; j < N; j++){ if(b[j] == 0) f = true; } } for(int k = 0; k < a[i].size(); k++) b[a[i][k]]--; break; } } } for(int i = 0; i < N; i++) printf("%d\n", ans[i]); printf("%d\n", (f)?1:0); return 0; }