第６回日本情報オリンピック 本選 「最悪の記者」

• 部分点解法

1. N個のチームの順位のつけ方をすべて試し、適する順位を求める。計算量はO(N!)であり、これでは全体の30%しか得点を得られない。

• 満点解法

1. トポロジカルソートをする。

計算量はO(N + M).これについてはJOIの解説と全く同じなのでそちらを参照してほしい。
（JOI解説の解法3をためしてみたけどTLEになる、、、だれかやりかた教えてください.結局解法4で解きましたが）

#include <cstdio>
#include <vector>

using namespace std;

int n,m;
bool ch[5003];
vector<int> G[5003];
int ans[5003],nau = 0;

void topo(int x){
  for(int i = 0;i < G[x].size();i++){
    int tmp = G[x][i];
    if(ch[tmp] == true)continue;
    topo(tmp);
  }
  ans[nau++] = x;
  ch[x] = true;
}

int main(){

  scanf("%d%d",&n,&m);
  
  for(int i = 0;i < m;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    G[b].push_back(a);
  }
  
  for(int i = 1;i <= n;i++){
    if(ch[i] == true) continue;
    topo(i);
  }
  
  
  for(int i = 0;i < n;i++){
    printf("%d\n",ans[i]);
  }
  bool ans2 = false;
  for(int i  = 0;i < n - 1;i++){
    bool flag = false;
    int a = ans[i];
    int b = ans[i+1];
    for(int j = 0;j < G[b].size();j++){
      if(G[b][j] == a){
	flag = true; 
	break;
      }
    }
    
    if(flag == false){
      ans2 = true;
      break;
    }
  }
  if(ans2){
    printf("1\n");
  }else{
    printf("0\n");
  }
  
  return 0;
}