[JOI精進録] 難易度7「最悪の記者」(第6回日本情報オリンピック 本選D)
問題リンク
問題概要
大会が開催され、一部の試合の結果が渡される。
この結果には引き分けはなく、全てのチームに異なる順位が付き、どの試合でも順位が上のチームが勝利した。
この試合結果に矛盾しない順位表を一つ出力し、また考えられる順位表は一つだけか判定しなさい。
解説
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; }