[백준] 10159번 - 저울 (C++) 문제 및 풀이

초코칩프라푸치노 2022. 3. 11. 11:48

문제) 백준 - 플루이드 와샬 - 저울

10159번: 저울

첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩

www.acmicpc.net

N이 최대 100이므로 플루이드 와샬(O(N^3))로 충분히 해결할 수 있습니다. 대소 관계가 중요하므로 그 관계에 따라 1 또는 -1로 표현합니다. 만약 같은 t, i, j에 대하여 (i, t)와 (t, j)의 관계가 같으면 (i, j)의 관계로 표현합니다.

C++ 소스코드)