[백준 2458] 키 순서

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

풀이

https://www.acmicpc.net/problem/10159 와 거의 동일한 플로이드와샬 알고리즘문제입니다 !

키를 비교할 수 있는 학생의 수는 그 학생보다 키가 작거나 키가 크거나, 이 둘중 하나는 무조건 해당되야합니다.

즉, 비교하고자 하는 학생(X)은 X를 거치는 학생과 X에서 뻗어나가는 학생의 수가 총원이되어야합니다. 

X가 모든학생이 연결되어있어야 한다는것입니다.

X와 연관이없는(x와 이어지는 노드가 없는 경우) 학생이 한명이라도 있다면, 문제의 조건을 어긋나게됩니다.!

코드

#include<iostream>
using namespace std;
int map[501][501];
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int n, m, a, b;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		map[a][b] = 1;
	}
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (map[i][k] && map[k][j])
					map[i][j] = 1;
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		int cnt = 0;
		for (int j = 1; j <= n; j++)
		{
			//본인은 제외하기
			if (i == j)continue;
			//학생->X &&X->학생 루트가 하나라도 없다면
			if (map[i][j] == 0 && map[j][i] == 0)
				//체킹
				cnt++;
		}
		//cnt=0 ? 모두연결되었다 
		//cnt>1 ? 연결되지않은 노드가있다.
		if (cnt == 0)ans++;
	}
	cout << ans<<'\n';
}

결과