Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 13 Mar, 2021

Easy

```
Consider the array ARR = { 0, 2, 1 } having 3 elements.
Starting at Block 0, you can move to only Block 0 and you cannot move to any other blocks.
Starting at Block 1, you can move between Block 1 and Block 2.
Starting at Block 2, you can move between Block 2 and Block 1.
Hence, the maximum number of distinct that you can visit is 2 in this case.
```

```
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains an integer, 'N,’ denoting the number of elements in the array 'ARR'
The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.
```

```
For each test case, return the maximum number of distinct blocks that you can reach by starting from an arbitrary block.
```

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10
1 <= N <= 10^5
0 <= ARR[i] < N
All elements of the array ARR are pairwise distinct.
Time limit: 1 sec
```

The idea is to traverse all the blocks one by one and find the number of distinct blocks that are reachable from that block. To find the number of different blocks that we can reach starting from a particular block, we will move through all the blocks that are reachable from that particular block and count the number of distinct blocks that we can visit. There is a simple method to keep track of the count of different blocks. Let us start from any arbitrary block **'K'** and traverse through the blocks that are reachable from block **'K' **until we come back to block **'K'** again. In any such path, all the blocks between the two occurrences of Block **'K' **will be distinct. Therefore, the number of distinct blocks will always be equal to the number of blocks that we have traversed before reaching Block **'K' **for the second time. Using the above approach, we will iterate through each block and find the number of reachable blocks for that block. In the end, we will return the maximum number of blocks that are reachable from a particular block.

- Let
**'MAX_DISTINCT_BLOCKS'**be a variable that stores the maximum number of distinct blocks that are reachable by starting from an arbitrary block. Initialize it as 0. - Iterate through ‘
**i’ = 0**to ‘**N - 1’**- Define the two variables
**'CURRENT_BLOCK'**and**'DISTINCT_BLOCKS_VISITED'**to store the index of the current block and the number of distinct blocks in the path, respectively. Initialize**'CURRENT_BLOCK'**as**i,**and initialize**'DISTINCT_BLOCKS_VISITED'**as 1, as we are starting from Block**i**. - While
**ARR['CURRENT_BLOCK']**is not equal to**i**- Update
**'CURRENT_BLOCK'**to**ARR['CURRENT_BLOCK']**. - Increase
**'DISTINCT_BLOCKS_VISITED'**by 1.

- Update
- Update
**'MAX_DISTINCT_BLOCKS'**to the maximum value among**'MAX_DISTINCT_BLOCKS'**and**'DISTINCT_BLOCKS_VISITED'.**

- Define the two variables
- Return the variable
**'MAX_DISTINCT_BLOCKS'**.

The idea is to optimize the previous approach by ensuring that all the blocks are being visited no more than two times. First of all, we need to observe that all ‘**N’ **blocks can be divided into a certain number of cyclic paths, where no two cycles have a common block. So whenever we are visiting a particular block, we are visiting all such blocks that belong to the same cycle as that block. Note that the number of blocks visited for all the nodes belonging to the same cycle will be equal. Therefore, it is redundant to calculate the answer for all members of the cycle separately. To ensure that we are not calculating any redundant answers, we will mark all the blocks that are being visited so that when we reach any such block the next time, we do not calculate the answer for it. To mark an element as visited, we will replace it with -1.

- Let ‘
**MAX_DISTINCT_BLOCKS’**be a variable that stores the maximum number of distinct blocks that are reachable by starting from an arbitrary block. Initialize it as 0. - Iterate through ‘
**i’ = 0**to ‘**N - 1’**- Define the two variables ‘
**CURRENT_BLOCK’**and ‘**DISTINCT_BLOCKS_VISITED’**to store the index of the current block, and the number of distinct blocks in the path, respectively. Initialize ‘**CURRENT_BLOCK’**as ‘**i’,**and initialize ‘**DISTINCT_BLOCKS_VISITED’**as 0, as we will start iterating from Block ‘**i’**. - While
**ARR[CURRENT_BLOCK]**is not equal to -1, then- Store
**ARR[CURRENT_BLOCK]**in a temporary variable ‘**TEMP’**. - Update ‘
**ARR[CURRENT_BLOCK]’**to -1. - Update ‘
**CURRENT_BLOCK’**to**‘TEMP’.** - Increase ‘
**DISTINCT_BLOCKS_VISITED’**by 1.

- Store
- Update ‘
**MAX_DISTINCT_BLOCKS’**to the maximum value among ‘**MAX_DISTINCT_BLOCKS’**and ‘**DISTINCT_BLOCKS_VISITED’.**

- Define the two variables ‘
- Return the variable ‘
**MAX_DISTINCT_BLOCKS’**.