Given a directed graph of N
nodes where each node is pointing to any one of the N nodes (can possibly point to itself). Ishu, the coder, is bored and he has discovered a problem out of it to keep himself busy.
The problem is as follows:
A node is 'good'
if it satisfies one of the following:
- It is the special node (marked as node 1)
- It is pointing to the special node (node 1)
- It is pointing to a good node.
Ishu is going to change the pointers of some nodes to make them all 'good'. You have to find the min. the number of pointers to change in order to make all the nodes good
(Thus, a Good Graph).Note
: Resultant Graph should hold the property that all nodes are good and each node must point to exactly one node.
1 <= N <= 100,000Input Format
A vector of N integers containing N numbers all between 1 to N, where i-th number is the number of node that i-th node is pointing to.Output Format
An Integer denoting min. number of pointer changes.Example Input
A = [1, 2, 1, 2]
A = [3, 1, 3, 1]
Pointer of node 2 is made to point to node 1
Pointer of node 3 is made to point to node 1
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified.
Still have a question? Checkout Sample Codes for more details.