코드

# 5 4
# 2 1
# 4 3
# 5 1
# 4 2
import sys

N,M = map(int,input().split(" "))

heavy_list = [[] for _ in range(N+1)] 
light_list = [[] for _ in range(N+1)] 

for _ in range(M):
    heavy, light = map(int, sys.stdin.readline().split())
    heavy_list[heavy].append(light)
    light_list[light].append(heavy)



def DFS(list, num):
    global cnt

    if visited[num] == False:
        cnt += 1
        visited[num]=True
        
        for n in list[num]:
            DFS(list, n)
    

result = 0

for i in range(1,N+1):
    visited = [False for _ in range(N+1)]
    cnt = -1
    DFS(heavy_list,i)
    if cnt >= (N+1)/2:

        result += 1

    visited = [False for _ in range(N+1)]
    cnt = -1
    DFS(light_list,i)
    if cnt >= (N+1)/2:

        result += 1

print(result)

풀이

• 무거운 것과 가벼운 것 따로 찾기.