読者です 読者をやめる 読者になる 読者になる

AOJ 0519 最悪の記者

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0519
基本的だけど面白い。
 総当たり戦をしたときの順位表を考える。
 順位は aの順位 < bの順位 なら aはbに必ず負けていない というので決まる。
 これはa → bという有向辺を貼ったときのトポロジカル順序そのものだ。
 問題の要求はいくつか勝敗を与えるからありうるのをどれでもいいから出力しろ、ということなのでトポロジカルソートしたものをそのまま出力すればよい。
 この手の問題だと閉路検出して順位表を作れない場合は-1を~とかいうのが定番だが、今回はそのかわりにトポロジカルソートの結果が一意かどうか出力しろ、というのがある。これは幅優先探索したとき、一段階に二つ以上状態があるかどうかをみればいい。

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

bool topologicalSort(const vector<vector<int>>& adj, vector<int>& ord) {
    int N = adj.size();
    vector<int> deg(N);//入次数
    for(int i = 0; i < N; ++i)
      for(int nv : adj[i])
        ++deg[nv];
    ord.assign(N, -1);
    int t = 0;

    bool isOnly = true;
    for(int v = 0; v < N; ++v) 
      if(deg[v] == 0)
        ord[t++] = v;
    isOnly &= t == 1;
    for(int h = 0; h < t; ++h) {
        int v = ord[h];
        int upd = 0;
        for(int nv : adj[v]) {
            --deg[nv];
            if(deg[nv] == 0)
              ord[t++] = nv, ++upd;
        }
        isOnly &= upd < 2;
    }
    return isOnly;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    for(int _ : in(m)) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].emplace_back(v);
    }
    vector<int> ord;
    bool only = topologicalSort(adj, ord);
    for(int x : ord) cout << x + 1 << endl;
    cout << !only << endl;
    return 0;
}

 JOIの問題、典型的だけど面白いという感じで良い。高校生のうちからこんなことをしていたらそりゃ頭も良くなるわな、という感じ。
 僕が高校生の頃なんて……という話をしようかと思ったが色々とダメすぎて悲しくなるのでやめた。