[파이썬] 정확한 순위

문제

시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부분만 가지고 있다.

A번 학생의 성적이 B번 학생의 성적보다 낮다면 화살표가 A -> B를 가리키도록 할 때 성적 결과를 다음과 같이 나타낼 수 있다.

 

유추해서 성적을 정확히 알 수 있는 학생도 있고 알수 없는 학생도 있다. 학생들의 성적을 비교한 결과가 주어질 때, 성적 순위를 정확히 알 수 있는 학생은 모두 몇명인지 계산하는 프로그램을 작성하시오

 

입력예시

6 6
1 5
3 4
4 2
4 6
5 2
5 4

풀이

#4로 올수있거 갈 수  있느 노드를 구하자
INF = int(1e9)
n,m = map(int,input().split())
graph = [[INF] *(n+1)for _ in range(n+1)]
cnt = 0
result = 0
#플로이드 워셜
#본인에서 본인으로 가는것 0으로 초기화
for a in range(1,n+1):
    for b in range(1,n+1):
        if a == b:
            graph[a][b] = 0

#받은 수 1로 초기화
for _ in range(m):
    x,y = map(int,input().split())
    graph[x][y] = 1

#워셜
for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1,n+1):
            graph[a][b] = min(graph[a][b],graph[a][k]+graph[k][b])

#오는것과 가는것이 가능한 노드수가 총 노드수와 같으면 오고 가는것 모두 가능하다는 뜻 
for a in range(1,n+1):
    cnt = 0
    for b in range(1,n+1):
        if graph[b][a] != INF or graph[a][b] != INF:
            cnt += 1
    if cnt == n:
        result += 1

print(result)