이번 문제는 BFS를 통해 해결하였다. a와 b를 입력받으면, a보다 가벼운 b는 heavy[a]에 담고, b보다 무거운 a는 light[b]에 담았다. 그리고 BFS를 통해 heavy와 light를 모두 탐색하여 두 탐색에서 한번도 방문하지 않은 노드가 있다면 그 노드는 현재 노드와의 무게 비교 결과를 알 수 없게 되므로 그 수를 세어 출력해주는 방식으로 해결하였다.

Code

from collections import deque
n = int(input())
m = int(input())
heavy = [[] for _ in range(n+1)]
light = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    heavy[a].append(b)
    light[b].append(a)
def bfs(cur):
    hq = deque()
    lq = deque()
    hq.append(cur)
    lq.append(cur)
    h_visited = [False for _ in range(n+1)]
    h_visited[cur] = True
    l_visited = [False for _ in range(n+1)]
    l_visited[cur] = True
    result = 0
    while hq:
        cur = hq.popleft()
        for nxt in heavy[cur]:
            if not h_visited[nxt]:
                h_visited[nxt] = True
                hq.append(nxt)
    while lq:
        cur = lq.popleft()
        for nxt in light[cur]:
            if not l_visited[nxt]:
                l_visited[nxt] = True
                lq.append(nxt)
    for i in range(1, n+1):
        if not h_visited[i] and not l_visited[i]:
            result += 1
    return result
for i in range(1, n+1):
    print(bfs(i))