[BOJ] 2458 : 키 순서 - travelbeeee

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

---

플로이드와샬 경로탐색

 키 순서를 입력으로 받아 그래프를 그린다고 생각하자. 그러면 i번 사람에서 j번 사람으로 경로가 있다면, j번 사람이 i번 사람보다 확실히! 키가 크다는 걸 의미한다. 따라서, 우리는 K번 사람이 다른 모든 사람들과 경로가 존재한다면 키 순서를 확실히 알 수 있다. 따라서, 플로이드와샬 알고리즘으로 모든 사람에 대해서 경로를 구하고, K번 사람이 다른 모든 사람들에게 갈 수 있거나, 혹은 다른 사람들이 K번 사람으로 올 수 있는 경로가 있다면 키 순서를 확실히 알 수 있는 사람으로 간주하면 된다.

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

const int INF = 99999999;
int map[501][501];

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

	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			map[i][j] = INF;
	for (int i = 1; i <= N; i++)
		map[i][i] = 0;

	for (int i = 0, x, y; i < M; i++) {
		cin >> x >> y;
		map[x][y] = 1; // x -> y
	}

	// 플로이드와샬
	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		bool check = true;
		for (int j = 1; j <= N; j++)
			if (map[i][j] == INF && map[j][i] == INF) {
				check = false;
				break;
			}
		if (check)
			ans++;
	}
	cout << ans;
	return 0;
}

---