🔥

문제

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 학생들의 수 N (2≤N≤500)과 두 학생 키를 비교한 횟수 M (0≤M≤N(N−1)/2) 이 주어진다. 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다.

출력

자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다.

예제 1 입력

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

예제 1 출력

1

예제 2 입력

2 1
1 2

예제 2 출력

2

Source

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

tall = [[] for _ in range(n + 1)]
small = [[] for _ in range(n + 1)]
check = [0 for _ in range(n + 1)]

for i in range(m):
	a, b = map(int, input().split())
	tall[a].append(b)
	small[b].append(a)

def dfs(edge, v):
	if(check[v] == 1):
		return 0
	check[v] = 1

	cnt = 1
	for u in edge[v]:
		# 현재 노드를 포함한 부분 그래프의 크기 누적
		cnt += dfs(edge, u)

	return cnt

cnt = 0

for i in range(1, n + 1):
	tall_cnt = 0
	small_cnt = 0

	for j in range(1, n + 1):
		check[j] = 0
	tall_cnt = dfs(tall, i) - 1

	for j in range(1, n + 1):
		check[j] = 0
	small_cnt = dfs(small, i) - 1

	if(tall_cnt + small_cnt == n - 1):
		cnt += 1

print(cnt)

참고