1889 선물 교환

풀이

• 위상정렬에서 정렬보다 전입차수 (Indegree)에 초점을 둔 풀이
• 어느 한 학생이 2개를 초과한 선물을 받는다 라는 것은 다른 한 학생은 선물을 1개 이하로 받는다 로 해석이 가능하다

1. 선물을 1개 이하 (Indegree < 2) 인 학생은 이벤트에서 제외한다.
2. 이벤트에서 제외된 학생에게 선물을 받을 예정이었던 두 학생의 선물 감소 (Indegree --)
3. 이벤트에 참여하는 학생이 모두 선물을 2개만 받을 때까지 1-2 과정을 반복한다.

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
graph = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)
student = set([i for i in range(1, n + 1)])

for i in range(1, n + 1):
    a, b = map(int, sys.stdin.readline().split())
    graph[i].append(a)
    graph[i].append(b)

    indegree[a] += 1
    indegree[b] += 1

queue = deque()
for i in range(1, n + 1):
    if indegree[i] < 2:
        queue.append(i)

while queue:
    s = queue.popleft()
    if s in student:
        student.remove(s)
    else:
        continue

    for g in graph[s]:
        indegree[g] -= 1
        if indegree[g] < 2:
            queue.append(g)

sys.stdout.write(str(len(student)) + '\n')
print(*list(student))

1889 선물교환