AOJ 0519 Worst Reporter

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0519

解法

a が b に勝利したことを，a -> b と有向辺で表現することにすれば，この問題はトポロジカル順序を求める問題になる．
トポロジカル順序が求まったら，その頂点列のなかで隣り合っていて，かつその頂点間に辺が存在していないものがあるかを考える．
存在していれば，順位は一意に定まらない．

最悪の記者だからトポロジカル順序に矛盾があるような入力があるかと思ったらそうでもなかった．最悪の記者でもなさそう（ほんまか）．

ソースコード

#include <bits/stdc++.h>
using namespace std;

void dfs(vector<vector<int>> const& g, int v, vector<bool>& used, vector<int>& res) {
    if(!used[v]) {
        used[v] = true;
        for(auto to : g[v]) {
            dfs(g, to, used, res);
        }
        res.push_back(v);
    }
}

vector<int> tsort(vector<vector<int>> const& g) {
    vector<bool> used(g.size());
    vector<int> res;
    for(int i=0; i<g.size(); ++i) {
        dfs(g, i, used, res);
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for(int i=0; i<m; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
    }
    auto res = tsort(g);
    bool f = true;
    for(int i=0; i<n-1; ++i) {
        bool f2 = false;
        for(int j=0; j<g[res[i]].size(); ++j) {
            f2 |= g[res[i]][j] == res[i+1];
        }
        f &= f2;
    }

    for(auto x : res) {
        cout << x+1 << endl;
    }
    cout << !f << endl;
}