Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Guaranteed Job
0 like 0 dislike
in Online Assessments by Expert (35,210 points) | 540 views

1 Answer

0 like 0 dislike
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.




Assumptions: N=3




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.




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


Sample Input 01:


2 4 3 1 4




3 3 1 3 4
by Expert (35,210 points)