Maximum Distinct Blocks

Posted: 13 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given 'N' blocks which are numbered from 0 to 'N' - 1 and are arranged in a straight line. Each block has an integer label on it which denotes the index of the next block that you can go to from that block. The labels on each block are given in the array 'ARR'. Your task is to find out the maximum number of distinct blocks that you can reach by starting from any arbitrary block and moving through all the blocks that you are allowed to move from that block and all other subsequent blocks.

For example:

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. 
Input Format:
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'.
Output Format:
For each test case, return the maximum number of distinct blocks that you can reach by starting from an arbitrary block. 
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^5 
0 <= ARR[i] < N

All elements of the array ARR are pairwise distinct.

Time limit: 1 sec
Approach 1

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.

 

Steps: 

  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.
  2. 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 'MAX_DISTINCT_BLOCKS' to the maximum value among 'MAX_DISTINCT_BLOCKS' and 'DISTINCT_BLOCKS_VISITED'.
  3. Return the variable 'MAX_DISTINCT_BLOCKS'.
Try Problem