AOJ 0119 Taros Obsession
問題
(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0119)。
解法
なんか論理の問題かな、推論とかするのかなと思っていたら、
(きこえますか...あなたの脳内に...直接語りかけています...トロピカル...いえ...トポロジカルソートを使うのです)
って聞こえたので。 http://www.prefield.com/algorithm/さんを参考にして実装しました。
コード
struct Edge{ int src, dst; Weight weight; Edge(int src, int dst, Weight weight): src(src), dst(dst), weight(weight){} }; bool operator<(const Edge &e, const Edge &f){ return e.weight != f.weight ? e.weight > f.weight : e.src != f.src ? e.src > f.src : e.dst > f.dst; } typedef vector<Edge> Edges; typedef vector<Edges> Graph; typedef vector<Weight> Array; typedef vector<Array> Matrix; bool visit(const Graph &g, int v, vector<int> &order, vector<int> &color){ color[v] = 1; FOR(e, g[v]){ if(color[e->dst] == 2) continue; if(color[e->dst] == 1) return false; if(!visit(g, e->dst, order, color)) return false; } order.push_back(v); color[v] = 2; return true; } bool topologicalSort(const Graph &g, vector<int> &order){ int n = g.size(); vector<int> color(n); rep(u, n) if(!color[u] && !visit(g, u, order, color)) return false; reverse(ALL(order)); return true; } int main(){ int m, n, x, y; scanf("%d%d", &m, &n); Graph g(m); rep(i, n){ scanf("%d%d", &x, &y); x--; y--; g[x].push_back(Edge(x, y, 1)); } vector<int> res; if(topologicalSort(g, res)){ rep(i, res.size()) printf("%d\n", res[i]+1); } return 0; }