AOJ 0519 - Worst Sportswriter
問題文 : 最悪の記者
解法 :
トポロジカルソートをすればよい.
トポロジカル順序が複数あるかどうかは, 隣り合う2 つの順位について, 互いへ直接たどり着けるかどうかを判定すれば良い.
(隣り合う順位へ直接辿りつけないのであれば, その2 つを仲介する順位が存在するからこれでよい.)
トポロジカルソートにO(m), 互いへたどり着けるかの判定がO(m)で, 計O(m) 時間でこの問題を解くことが出来る.
#include <cstdio> #include <vector> using namespace std; bool other; bool vis[5000]; vector<int> win[5000], lose[5000], ord; void dfs(int v) { vis[v] = true; for (int i = 0; i < win[v].size(); i++){ if (!vis[win[v][i]]) dfs(win[v][i]); } ord.push_back(v); } int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < m; i++){ int a, b; scanf("%d %d", &a, &b); win[--a].push_back(--b); lose[b].push_back(a); } int cnt = 0; for (int i = 0; i < n; i++) if (lose[i].size() == 0) dfs(i); for (int i = n - 1; i >= 0; i--){ printf("%d\n", ord[i] + 1); if (i){ bool ok = true; for (int j = 0; j < win[ord[i]].size(); j++) if (win[ord[i]][j] == ord[i - 1]) ok = false; other |= ok; } } printf("%d\n", other); return (0); }