2458번: 키 순서
1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여
www.acmicpc.net
문제만 읽어서는 감이 잘 오질 않는데, 결과적으로 본인의 키가 몇번째인지를 알려면 기술되어있는 N명의 '학생중 자신보다 키가 작은 학생의 수 + 자신보다 키가 큰 학생의 수 = N-1'이 되면 되는데, 이건 플로이드-워셜 알고리즘을 조금 응용하면 문제를 풀 수 있다. 알고리즘에 대한 설명은 나보다는 위키가 훨씬 더 잘 알려주니...
플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서, 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고
ko.wikipedia.org
#include <stdio.h>
#include <string.h>
#define UNKNOWN 0x00
#define TALL 1
#define SMALL -1
int N, M;
int floid[501][501];
int main()
{
memset(floid, UNKNOWN, sizeof(floid));
scanf("%d%d", &N, &M);
for (int i = 0; i < M; i++)
{
int a, b;
scanf("%d%d", &a, &b);
floid[a][b] = TALL;
floid[b][a] = SMALL;
}
for (int k = 1; k <= N; k++)
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (floid[i][j] == UNKNOWN)
{
if (floid[i][k] == TALL && floid[k][j] == TALL)
floid[i][j] = TALL;
if (floid[i][k] == SMALL && floid[k][j] == SMALL)
floid[i][j] = SMALL;
}
}
}
}
int answer = 0;
for (int i = 1; i <= N; i++)
{
bool existUNKNOWN = false;
for (int j = 1; j <= N; j++)
{
if (i != j && floid[i][j] == UNKNOWN)
{
existUNKNOWN = true;
break;
}
}
if (!existUNKNOWN)
{
answer += 1;
}
}
printf("%d\n", answer);
return 0;
}