POJ 3660 Cow Contest

問題

1からNまでのラベルが付いたノードが与えられる。このグラフの有効辺がM個与えられる。トポロジカル順序が厳密に決まっているノード数を返せ。

やりかた

トポロジカルソートできるグラフだとして、あるノードのトポロジカル順序が厳密に決まっている場合は、自分以外のノード全てで

1. 自分からそのノードへ到達できる
2. そのノードから自分へ到達できる

のどちらかに分類できる場合である。どちらも成立する場合はループが起きているのでNG。どちらも成立しない場合は2ノード間で順序が定まらないのでNG。これに適合するノードの数を数えればいい。

ワーシャルフロイドで接続関係を調べたのでO(V^3)。
以下ソース。

int main(int argc, char **argv){
  int N, M;
  scanf("%d %d", &N, &M);
  
  vector<vector<bool> > E(N, vector<bool>(N, false));
  for(int i = 0; i < M; i++){
    int s, t;
    scanf("%d %d", &s, &t);
    E[t - 1][s - 1] = true;
  }
  for(int i = 0; i < N; i++) E[i][i] = true;
  
  for(int k = 0; k < N; k++)
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++)
	E[i][j] = E[i][j] | (E[i][k] && E[k][j]);//Warshall-Floyd

  int ans = 0;
  for(int i = 0; i < N; i++){
    int cnt = 0;
    for(int j = 0; j < N; j++)
      if(i != j) cnt += (E[i][j] ^ E[j][i]);//i->jかj->iのどちらかのみが成立するケースを数える
    ans += (cnt == N - 1);
  }
  cout << ans << endl;
  return 0;
}