[JOI精進録] 難易度7「最悪の記者」(第6回日本情報オリンピック 本選D)

問題リンク

atcoder.jp

問題概要

大会が開催され、一部の試合の結果が渡される。
この結果には引き分けはなく、全てのチームに異なる順位が付き、どの試合でも順位が上のチームが勝利した。
この試合結果に矛盾しない順位表を一つ出力し、また考えられる順位表は一つだけか判定しなさい。

解説

AC解法 (20/20点)

トポロジカルソートをすればよいです。
トポロジカルソートは入次数が0になっている頂点を順にqueに追加、探索すれば作成できます。
このときqueに入っている要素の数は0もしくは1の場合は他の選択肢がないですが、それ以外の場合はそちらを選択することも可能です。
そのためqueのサイズを監視することで判定が可能です。

ACコード

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

int main(){
  int n,m,r(0); cin >> n >> m;
  vector<vector<int>> G(n); vector<int> B(n),R;
  for (int i(0),a,b;i < m;++i) (cin>>a>>b),G[a-1].emplace_back(b-1),++B[b-1];
  queue<int> que;
  for (int i(0);i < n;++i) if (B[i]==0) que.emplace(i);
  while(!que.empty()){
    auto x = que.front(); que.pop();
    if (!que.empty()) r=1;
    R.emplace_back(x+1);
    for (auto a:G[x]){
      --B[a];
      if (B[a]==0) que.emplace(a);
    }
  }
  for (auto a:R) cout << a << '\n';
  cout << r << endl;
}

提出結果

atcoder.jp