POJ 1975 Median Weight Bead

問題

1からNの数字が書かれたビーズがある。2つビーズについての重さの関係の情報がM個ある。N個のビーズのうち重さが中央値になりえないものの個数を求めよ。

やりかた

一種のトポロジカルソート。自分より重いビーズに辺を張って、重さの関係をグラフに置き換える。自分から到達可能な点が(N+1)/2以上あればメディアンたりえないし、自分に到達可能な点が(N+1)/2以上あっても同様。到達可能性を調べるのはワーシャルフロイドでやった。グラフは木構造でない場合ももちろんあるのでDFSではそこ注意。

以下ソース。

bool d[100][100];

int main(int argc, char **argv){
  int T;
  cin >> T;
  while(T--){
    int N, M, s, t;
    cin >> N >> M;
    memset(d, false, sizeof(d));
    for(int i = 0; i < N; i++) d[i][i] = true;
    for(int i = 0; i < M; i++){
      cin >> s >> t; s--, t--;
      d[t][s] = true;
    }
    for(int k = 0; k < N; k++)
      for(int i = 0; i < N; i++)
	for(int j = 0; j < N; j++)
	  d[i][j] |= (d[i][k] && d[k][j]);

    int ans = 0;
    for(int i = 0; i < N; i++){
      int cnt1 = 0, cnt2 = 0;
      for(int j = 0; j < N; j++){
	cnt1 += d[i][j];
	cnt2 += d[j][i];
      }
      ans += (cnt1 > (N + 1) / 2);
      ans += (cnt2 > (N + 1) / 2);
    }
    cout << ans << endl;
  }
}