#P10933. Maximizing the Selection of World Elements
Maximizing the Selection of World Elements
Maximizing the Selection of World Elements
God possesses types of world elements. Each element can restrict exactly one other type of element. For each (), the element can restrict element . God plans to deploy a subset of these elements into a new space to construct a world. However, to ensure peace and tranquility, he requires that for every deployed (selected) world element, at least one world element that can restrict it is not deployed. In other words, if an element is deployed, then there must exist at least one index with such that the th element is not deployed.
Your task is to help God maximize the number of deployed world elements. Formally, let be the set of deployed elements. The condition is that for every , there exists some with and . Find the maximum possible size of .
inputFormat
The first line contains a single integer $N$ ($1 \le N \le 10^5$), the number of world elements.
The second line contains $N$ integers $A[1], A[2], \dots, A[N]$ ($1 \le A[i] \le N$, and it is allowed that $A[i]=i$ but note that each element restricts exactly one other element). These numbers describe the restriction relationship: element $i$ can restrict element $A[i]$.
outputFormat
Output a single integer: the maximum number of world elements that can be deployed while satisfying the condition that for every deployed element $j$, there exists at least one element $i$ (with $A[i] = j$) which is not deployed.
sample
3
2 3 2
1