[백준] 2458 키 순서 c++

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

2458번: 키 순서

 

풀이과정

일단 각 간선의 가중치를 1로 잡았다.  
자신의 키가 몇 번째인지 알 수 있으려면, 자신을 제외한 무한대가 아닌 노드들이 N - 1개여야 한다.

num[i][j] = 1이라는 것은 i보다 j가 크다는 뜻이고,  
num[j][i] = 1이라는 것은 i보다 j가 작다는 뜻이다.

이 두 가지 경우 다 i학생의 기준에서 키의 기준을 알 수 있다.  
그러므로 num[i][j] != INF 또는 num[j][i] != INF 일 때를 카운트해서  
N - 1개면 자신의 키가 몇 번째인지 알 수 있는 학생이다.

 

 

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int N, M, a, b;
int num[501][501];
const int INF = 1e9;

void floyd() {
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (num[i][j] > num[i][k] + num[k][j]) {
					num[i][j] = num[i][k] + num[k][j];
				}
			}
		}
	}
}

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

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if(i != j) num[i][j] = INF;
		}
	}

	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		num[a][b] = 1;
	}
	floyd();

	int res = 0;
	for (int i = 1; i <= N; i++) {
		int cnt = 0;
		for (int j = 1; j <= N; j++) {
			if (i == j) continue;
			// i보다 큰 사람이 존재 || i보다 작은 사람이 존재
			if (num[i][j] != INF || num[j][i] != INF) {
				cnt++;
			}
		}
		if (cnt == N - 1) res++; // 자신을 제외한 모든 정점과 연결
	}
	cout << res;
}