백준 Baekjoon 2458 키순서 풀이

사용언어

Visual studio 2019 C++

생각하기

플로이드 워샬 알고리즘 사용

플로이드 워샬 알고리즘

모든 정점들 사이의 최단경로를 구하는 알고리즘.

[2458 풀이]

#include <iostream>
using namespace std;
int N, M;
const int MAX = 500 + 1;
int student[MAX][MAX];

void floyd() {
	for (int i = 1; i <= N; i++) { // 중간
		for (int j = 1; j <= N; j++) { // 시작
			for (int k = 1; k <= N; k++) { // 끝
				if (student[j][k] == 0) {
					if (student[j][i] == 1 && student[i][k] == 1) 
						student[j][k] = 1;
					
					else if (student[j][i] == -1 && student[i][k] == -1) 
						student[j][k] = -1;
					
				}
			}
		}
	}
}

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

	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b;
		student[a][b] = -1; // a < b 
		student[b][a] = 1; // b > a
	}

	floyd();
	int cnt = 0;
	for (int i = 1; i <= N; i++) {
		int n = 0;
		for (int j = 1; j <= N; j++) {
			if (i == j)
				continue;
			if (student[i][j]) // 0 이 아니라면 두명중 누가 크고 작은지 알수있음
				n++;
		}
		if (n == N - 1)
			cnt++; // 키순서를 아는 사람의 수가 자신을 뺀 총 학생의 수와 같다면
	}
	cout << cnt << "\n";
}