Choose but not both
Practice
2.8 (13 votes)
Algorithms
Depth first search
Dynamic programming
Graphs
Trees
Problem
89% Success 1551 Attempts 50 Points 2s Time Limit 256MB Memory 1024 KB Max Code
The alone Y has another array \(a_1, a_2, ..., a_n\) that \(1 \leq a_i \leq n\). this time Y wants to choose some numbers from \(1\) to \(n\) that there is no \(i\) that both \(i\) and \(a_i\) is chosen.
What is the maximum amount of numbers that Y can choose?
Input
First line contains only \(n\), legnth of array.
Second line contains the array elements \(a_1, a_2, ..., a_n\)separated by space.
\(1 \leq n \leq 3 \times 10^5\)
\(1 \leq a_i \leq n\)
Output
The only line of output contains an integer, maximum amount of numbers that Y can choose.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
11 votes
Tags:
Fenwick TreeGraphsDepth First SearchDisjoint Set UnionAlgorithms
Points:50
4 votes
Tags:
Dynamic ProgrammingAlgorithmsGraphsDepth First Search
Points:50
8 votes
Tags:
Depth First SearchTreesMathematicsGraphsDynamic ProgrammingAlgorithms
Editorial
Login to unlock the editorial