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

키를 비교한 데이터를 주고 이 데이터를 기반으로 키 순위를 정확히 특정 가능한 사람의 수를 구하는 문제이다.
플로이드 워셜 알고리즘을 사용해야할 것 같은데 어떻게 사용하는지 까먹어서 BFS 두 번 돌려서 해결했다.

Python

from collections import defaultdict

n, m = map(int, input().split())

h = defaultdict(list)
H = defaultdict(list)

for _ in range(m):
  a, b = map(int, input().split())
  
  h[a].append(b)
  H[b].append(a)
  
ans = 0
for i in range(1, n+1):
  que = [i]
  idx = 0
  visited = [True] * (n+1)
  visited[i] = False
  
  while idx <len(que):
    now = que[idx]
    idx += 1
    
    for next in h[now]:
      if visited[next]:
        visited[next] = False
        que.append(next)
  rank = len(que) - 1
  
  que = [i]
  idx = 0
  visited = [True] * (n+1)
  visited[i] = False
  
  while idx < len(que):
    now = que[idx]
    idx += 1
    
    for next in H[now]:
      if visited[next]:
        visited[next] = False
        que.append(next)
  rank += len(que)

  if rank == n:
    ans += 1
    
print(ans)

키가 작은 방향으로 길이 열려있는 인접 그래프 h와 키가 큰 방향으로 열려있는 H를 만들고 각각 BFS를 돌렸다.
그렇게 되면 h에서는 i를 포함해서 i보다 키가 작은 사람들이 que에 저장되고, H에서는 그 반대가 저장된다.
마지막으로 각 que의 길이를 더하고 1을 뺐을 때 그 합이 전체 인원수가 된다면 해당 i는 순위를 특정할 수 있는 사람이 된다.

n이 최대 500이라 500 * 1000 정도 복잡도가 생길 것이라 판단해서 해봤는데 실제로 돌아가서 다행이다. 플로이드 워셜로 하면 더 빨리 해결할 수 있을 듯 한데 공부를 해야겠다.