문제 태그

• 그래프
• 너비 우선 탐색
• 도달 가능성

한국어 문제 해석

아이템은 1번부터 N번까지 있다. 처음에는 1번 아이템만 가지고 있다.

친구 i에게 $A_i$번 아이템을 주면 B_i번 아이템을 받을 수 있다. 이 교환을 통해 최종적으로 얻을 수 있는 아이템 종류 수를 구한다. 처음부터 가지고 있는 1번 아이템도 개수에 포함한다.

문제 요약

• 교환 정보 $A_i$, $B_i$는 방향 간선 $A_i$에서 $B_i$로 볼 수 있다.
• 처음 가진 아이템은 1번이다.
• 1번에서 시작해 도달 가능한 정점 수가 답이다.

예시 워크스루

첫 번째 예시의 간선은 1에서 2, 2에서 3, 3에서 4, 2에서 4, 5에서 2다.

• 처음 방문한 정점은 1이다.
• 1에서 2로 갈 수 있으므로 2를 얻을 수 있다.
• 2에서 3과 4로 갈 수 있으므로 3, 4를 얻을 수 있다.
• 5에서 2로 가는 간선은 있지만 5 자체를 얻을 방법이 없으므로 사용할 수 없다.
• 도달 가능한 정점은 1, 2, 3, 4로 총 4개다.