aoj0519:Worst Sportswriter

問題文

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

解法

勝利したチームから敗北したチームに辺を引く。すると、閉路のない有向グラフ(DAG)になる。
　
DAGは必ず順序付け(トポロジカルソート)できることが知られており、それによって得られた順序こそがこの問題で求められているものである。

トポロジカルソートはくらいの計算量で行うアルゴリズム(dfsのついでにやるやつ)が有名だが、この問題の制約的にのやつでも間に合うのでそっちでやった。具体的には、まずすべての頂点の入次数を求めておく。そして答えを格納する配列を用意する。その上で、以下の手順を繰り返す。
入次数が0の頂点を1つ選び、答えを格納する配列に追加する。存在しなかったら終了
で選んだ頂点を始点とするすべての辺を選び、それぞれの辺について終点となる頂点の入次数を1減らす。
で選んだ頂点の入次数を-1にして、に戻る。

　複数の順位表が存在するか、ということを調べるときには先程求めた順位表において、隣り合う順位のチームであって勝敗がはっきりしていないようなチームのペアが存在するかどうかを調べればよい。

コード

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

int N,M;
vector<int>G[5000];

int main(){
    int D[5000]={0};
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        G[--a].push_back(--b);
        D[b]++;
    }

    vector<int>ans;

    for(int _=0;_<N;_++){
        for(int i=0;i<N;i++){
            if(D[i])continue;
            ans.push_back(i);
            for(int j=0;j<G[i].size();j++){
                D[G[i][j]]--;
            }
            D[i]=-1;
            break;
        }
    }
    bool flag=false;
    for(int i=0;i<N-1;i++){
        int v=ans[i];
        flag|=find(G[v].begin(),G[v].end(),ans[i+1])==G[v].end();
    }

    for(int i=0;i<N;i++)printf("%d\n",ans[i]+1);
    printf("%d\n",flag);
    return 0;
}