백준
백준 10159 저울 (파이썬)
chldkato
2020. 2. 18. 01:04
https://www.acmicpc.net/problem/10159
10159번: 저울
첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 주어진다. 각 줄에는 측정된 물건 번호를 나타내는 두 개의 정수가 공백을 사이에 두고 주어지며, 앞의 물건이 뒤의 물건보다 더 무겁다.
www.acmicpc.net
1. 플로이드-와샬로 이동 가능한 모든 경로를 구한다
2. i에서 j로 갈 수 없고 j에서 i로 갈 수 없으면 무게를 비교할 수 없으므로 cnt를 증가
3. 자기자신을 비교한 경우를 제외하기 위해 cnt-1을 출력
import sys
INF = sys.maxsize
input = sys.stdin.readline
n, m = int(input()), int(input())
a = [[0]*n for _ in range(n)]
for _ in range(m):
x, y = map(int, input().split())
a[x-1][y-1] = 1
for k in range(n):
for i in range(n):
for j in range(n):
if a[i][k] and a[k][j]:
a[i][j] = 1
for i in range(n):
cnt = 0
for j in range(n):
if not a[i][j] and not a[j][i]:
cnt += 1
print(cnt-1)