[金貨4]2458号:鍵順

🛠 質問する
https://www.acmicpc.net/problem/2458
👩🏻‍💻 解決策
floydwalshアルゴリズム(すべての場所から他のすべての場所への最短経路)で解決できる問題.
最短パスをすべて更新して、背が自分より高いか低いかの人数がn-1(自分以外の人数)であれば、自分の身長が何番目の学生であるかを知ることができます
ソースコード

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[0] * (n+1) for _ in range(n+1)]

for _ in range(m):
  a, b = map(int, input().split())
  graph[a][b] = 1

for k in range(1, n+1):
  for a in range(1, n+1):
    for b in range(1, n+1):
      # a가 b보다 작을 경우
      if graph[a][k] == 1 and graph[k][b] == 1:
        graph[a][b] = 1

answer = 0
for i in range(1, n+1):
  cnt = 0
  for j in range(1, n+1):
    # 자신보다 키가 큰 사람과 작은 사람 수의 합
    cnt += graph[i][j] + graph[j][i]
  # 자신과 비교해서 키를 알고 있는 사람이 자신 제외한 수만큼(n-1) 있을 경우
  if cnt == n-1:
    answer += 1

print(answer)

💡 他人の解答
floydwalshアルゴリズムを用いるとpython 3でコミットするとタイムアウトするため,別の方法dfsを用いた解法である.

import sys
input = sys.stdin.readline

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

graph = [[] for _ in range(n)]

for _ in range(m):
  a, b = map(int, input().split())
  if b-1 not in graph[a-1]:
    graph[a-1].append(b-1)

def dfs(i, idx, graph):
  for j in graph[idx]:
    if not check[i][j]:
      check[i][j] = 1
      check[j][i] = 1
      dfs(i, j, graph)

check = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
  check[i][i] = 1
  dfs(i, i, graph)

answer = 0
for row in check:
  if row == [1] * n:
    answer += 1

print(answer)