Question

Number of trips | OA Coding Questions and Solutions | Set - 1 | 2023

Answer 1

Problem Statement:

 

You are given a map consisting of N cities. Each city has a directed path to another city or it can be to itself (this means, each city has exactly one outgoing edge).

 

You are given an array arr. There is a directed path from city i to arr[i] , where 1<=i<=N

 

You have to start from every city and then travel through cities until you reach a city that you have already visited before.

 

Task: For each city, determine the number of cities you would visit if you start from that city.

 

Note: 1-based indexing is followed in the problem.

 

Example:

 

Assumptions: N=3
arr=[2,3,1]

 

Approach:

 

You have three edges in the graph.
1st edge is from city 1 to city arr[0] that is city 2.
2nd edge is from city 2 to arr[1] that is city 3.
3rd edge is from city 3 to arr[2] that is city 1.
Starting from city1, you visit city 1,2 and 3. There is a path from city 3 to 1, but city 1 is already visited.
Starting from city2, you visit city 2,3 and 1. There is a path from city 1 to 2, but city 2 is already visited.
Starting from city1, you visit city 3,1 and 2. There is a path from city 2 to 3, but city 3 is already visited.
Thus, the answer array is [3,3,3]

 

Input Format:

 

First line is T , no of test cases.
For each test case, first line contains a single integer N, no of cities
the second line contains an array arr denoting the array containing the destination city for paths from each city.

 

Output Format:

 

For each test case, print N integers acc to problem statement.

 

Constraints:

 

1<=T<=100
1<=N<2x10^5
1<=arr[i]<=N for all 1<=i<=N
Sum of all N[i] <2x10^5 for all 1<=i<=T

 

Sample Input 01:

 

1
5
2 4 3 1 4

 

Output:

 

3 3 1 3 4