[伯俊]2458号キー順序

[伯俊]2458号基序

1.質問

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番以外の生徒たちは自分の身長がどれくらいなのか分からない.
学生の身長を比較するときは、自分の身長を知っている学生が何人いるかを計算し、プログラムを書いてください.

2.入力

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

3.出力

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

4.解答

2次元配列、全要素初期化INF鍵の順序を優先して入力します.

年下の生徒より年下と更新された.

私より年上の学生はみんな私より年上だと更新した.

更新完了後、行の中に1つ残っているINFとなると、順番がわからない生徒です.

INF余剰生徒数が出力されない.

5.最初のコードと異なる点

・i==jの場合はゼロではなく、同様にINFに初期化されているため、INFを保有している.i!=j && graph[i][j] == INF条件式改訂

6.コード

#include <iostream>
#include <algorithm>
#define INF 1e9
using namespace std;

int graph[501][501];

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int number_of_students, number_of_operation;
	cin >> number_of_students>>number_of_operation;

	for (int i = 1; i <= number_of_students; i++){
		for (int j = 1; j <= number_of_students; j++) {
			graph[i][j] = INF;
		}
	}

	for (int i = 0; i < number_of_operation; i++){
		int taller, smaller;
		cin >> taller >> smaller;
		graph[taller][smaller] = 1;
		graph[smaller][taller] = -1;
	}

	for (int k = 1; k <= number_of_students; k++){
		for (int i = 1; i <= number_of_students; i++) {
			for (int j = 1; j <= number_of_students; j++) {
				if (graph[i][j] == INF) {
					if (graph[i][k] == 1 && graph[k][j] == 1) graph[i][j] = 1;
					if (graph[i][k] == -1 && graph[k][j] == -1) graph[i][j] = -1;
				}
			}
		}
	}

	int answer = 0;
	for (int i = 1; i <= number_of_students; i++){
		bool has_INF = false;
		for (int j = 1; j <= number_of_students; j++) {
			if (i!=j && graph[i][j] == INF) {
				has_INF = true;
				break;
			}
		}
		answer += has_INF ? 0 : 1;
	}

	cout << answer;
}