아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

탐사대

면접 대비

시간 제한2초메모리 제한512 MB

요약
각 후보가 최대 한 명의 다른 후보와 함께 가기를 거부할 때, 거부 관계가 성립하지 않도록 최대 인원의 부분집합을 고른다.
난이도

보통10점 중 6점

유형
그래프, 그리디, 동적 계획법, 트리
정답자
아직 제출이 없습니다

문제

이웃 항성계로 탐사대를 보내려 한다. 1번부터 n번까지 번호가 붙은 n명의 후보 중에서 탐사대원을 선발한다. 주최자는 되도록 많은 후보를 탐사대에 보내고 싶다.

후보들을 대상으로 설문 조사를 했고, 각자는 다른 후보 중에서 함께 탐사대에 가기 싫은 사람을 최대 한 명까지 적을 수 있었다. i번 후보의 설문 결과는 정수 aia_i이며, i번 후보가 함께 가기 싫어하는 후보의 번호와 같다. i번 후보가 어떤 구성으로도 함께 갈 의향이 있다면 ai=−1a_i = -1이다.

이제 주최자는 누구를 탐사대에 보낼지 정해야 한다. 후보 i가 탐사대에 포함되고 ai≠−1a_i \ne -1이면 후보 aia_i는 탐사대에 포함되지 않도록 참가자를 선발하기로 했다. 주최자는 최대 인원의 탐사대를 만들고 싶어한다.

설문 결과가 주어졌을 때 탐사대에 보낼 수 있는 후보의 최대 인원을 구하는 프로그램을 작성하라.

입력

첫째 줄에 후보의 수를 나타내는 정수 nn이 주어진다 (1≤n≤300 0001 \le n \le 300\,000).

다음 nn개의 줄에는 설문 결과가 주어진다. 이 중 i번째 줄에는 i번 후보의 설문 결과인 정수 aia_i가 주어진다 (ai=−1a_i = -1 또는 1≤ai≤n1 \le a_i \le n, ai≠ia_i \ne i).

출력

한 줄에 탐사대에 보낼 수 있는 후보의 최대 인원을 나타내는 정수 하나를 출력한다.

예제2

  1. 예제 1

    입력
    4
    2
    4
    2
    1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    3
    2
    -1
    2
    
    예상 출력
    2