Backjunアルゴリズム2458号:キー順

リンク

https://www.acmicpc.net/problem/2458

質問する

1番からN番まで番号が貼られていた生徒について、2人の生徒の身長を比較し、結果の一部を得た.しかし、N人とも身長が異なると仮定する.例えば、6人の生徒に対して身長を6回しか比較しなかった結果、以下のようになった.

1番学生の身長<5番学生の身長

3番学生の身長<4番学生の身長

5番学生の身長<4番学生の身長

4番学生の身長<2番学生の身長

4番学生の身長<6番学生の身長

5番学生の身長<2番学生の身長
この比較結果から、すべての生徒の中で、一番背の小さい生徒から自分が何位であるかを知ることができ、以下のような図を描いて自分が何位であるかを簡単に確認することができる.a番学生の身長がb番学生の身長より小さい場合は、aからbまでの矢印で表します.

1番は5番より低く、5番は4番より低いので、1番は4番より低いです.では、1番、3番、5番はいずれも4番未満です.また、4番が2番と6番より小さいので、4番には自分より小さい学生が3人、自分より大きい学生が2人いて、自分の身長が何位なのか正確に知ることができます.しかし、4番以外の生徒たちは自分の身長がどれくらいなのか分からない.

学生の身長を比較するときは、自分の身長を知っている学生が何人いるかを計算し、プログラムを書いてください.

入力

第1行は、生徒数N(2≦N≦500)と2人の生徒の身長比較回数M(0≦M≦N(N−1)/2)を与える.次のM行は、2つの整数aおよびbを与え、2人の学生の身長を比較した結果を表す.これは、a番の学生がb番の学生より低いことを意味する.

しゅつりょく

自分の身長がどれくらい分かる学生が何人いるかを印刷します.

入力と出力の例

解法

やった問題をもう一度やる
質問では、自分の身長が分かる生徒数を求めるのは、自分以外の生徒がつながっていれば、身長順を正確に把握できるからです.
この場合,1の答えを増やすことで問題を解決する.
その他はコメントを参照してください.

プールコード（C++）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<tuple>
#include<functional>
#include<utility>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define MAX 501
#define INF 1e9
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;

int dist[MAX][MAX];

void resetGraph(){
  for(int i = 1; i < MAX; i++){
    for(int j = 1; j < MAX; j++){
      dist[i][j] = INF;
    }
  }
}

void floyd(int n){
  for(int k = 1; k <= n; k++){ // k : 거쳐가는 정점
    for(int i = 1; i <= n; i++){ // i : 행(출발 정점)
      for(int j = 1; j <= n; j++){ // j : 열(도착 정점)
       // 점화식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
}

int main(){
  fastio;
  int n,m;
  cin >> n >> m;
  resetGraph();
  for(int i = 0; i < m; i++){
    int a,b; cin >> a >> b;
    dist[a][b] = 1;
  }
  floyd(n);
  int ans = 0; // 정답
  for(int i = 1; i <= n; i++){
    int cnt = 0;
    for(int j = 1; j <= n; j++){
      if(dist[i][j] != INF || dist[j][i] != INF){ // 키가 작은 사람을 알거나 또는 키가 큰 사람을 알면
        cnt++;
      } 
    }
    if(cnt == n - 1) ans++; // 자기 자신을 제외한 모든 사람과 연결되어 있으면
  }
  cout << ans;
  return 0;
}